Skip to content

Instantly share code, notes, and snippets.



Last active Aug 16, 2016
What would you like to do?
Personal Package Manager TODO List


  • Eliminate POSIX imports from everything downstream of Basic.

  • Eliminate Utility module (clean up names here)

  • Clean up topological sort and closure algorithms

  • Speed up tests

  • Do explicit copy-in from PackageDescription types, instead of reusing them.

  • Eliminate downstream users of PackageDescription.

  • C language targets productization

  • PkgConfig productization

  • Need diagnostics infrastructure

  • Add ability to invoke swift-test in tests:

    1. Need public incremental toolchain scripts
  • Excise localFS from lowest-level components

  • Excise fopen() things.

  • Cache Module.recursiveDependencies, once model is immutable.

  • Move FileSystem to be class only protocol

    • I have second thoughts.... it ends up documenting behavior. Maybe use inout convention with it? No, that doesn't actually work correctly with a real struct.
  • Do PackageCore ModuleCore ProductCore thing (?)

  • Version ranges are broken, SwiftPM will accept pre-release of next version instead of exact dependency due to use of range.

  • Implement tests for PackageGraphLoader.

  • Git FileSystem features

    • Performance?
    • Funny names?
    • Symlinks?
  • Cross-package testing infrastructure

  • Make package init tests inside repo build.

Dependency TODO

  • DependencyResolver

  • SKIPPABLE: Caching manifest loader

  • swift package resolve [--url <URL>] [--version <version>] [--constraint <CONSTRAINT>]

    • needs checkout manager wired up
    • caching manifest loader
  • We need CheckoutManager to have an interface to update a given repository, and to define whether or not lookup does this. This is very important to have tests for, too.

  • Figure out submodule handling in clones.

Dependency Resolution


Root: [A > 0, B > 0, C > 0] A: { .2: [], .1: [] } B: { .2: [ A == .2 ], .1: [ A == .1 ] } C: { .1: [B == .1] }

This graph should always resolve, no matter what order we pick constraints.

Root: [A > 0, B > 0] A: { .2: [C == 0.1], .1: [] } B: { .2: [C == 0.2], .1: [] } C: { .1: [], .2: [] }

What version of C we pick depends on the order we choose to resolve constraints, which is unfortunate (among other things, it means changes to the resolution algorithm could break existing packages).


  • Goal is to always try and take latest stuff.

    This is based on a belief that it is what is best for the overall ecosystem, by encouraging adoption and migration forward. One can imagine strategies where the dependency resolution would actively, say, try not to take new minor releases that add otherwise unnecessary dependencies, but instead we should leave that up to the package.

  • It is a bad idea to look backwards for a dependency which "opens up" a constraint (e.g., B-.2 has a dep of C == .3, we shouldn't try and look at B-.1 to see if has a dep like C >= .1. This in theory would open up the solution space, and help in certain situations if we are trying to prioritize picking the latest version of C. However, based on the domain, it is likely this happened because B-.1 implicitly doesn't work with, say, C == .2 (and only later realized that).

  • Whether to be DFS or BFS:

    • It would seem that BFS is desirable, as it prioritizes all of the constraints of the packages closest to the root prior to processing ones deeper in the graph. For example, this allows the root package to directly control a picked version through the use of additional package constraints on what would otherwise be indirect dependencies (these may need to be added in a particular order). DFS allows this too, but in a less direct fashion (I think).

    • On the other hand, DFS enforces the desirable invariant that, the resolution of each individual package in the graph can be described simply as a resolution of the package plus some set of interacting constraints (the empty set, if none of other packages impose constraints on the package used in that graph). In BFS, this is not the case, the resolution of an individual package may interact in a more complicated fashion.

      • This is particular useful for debugging and reproducibility. Suppose an application finds they can no longer use package P at version V (it does not resolve). The package manager can support a feature which explains:

        P@V is unresolvable with the external constraints [P2@V2, P3@V3]

        which package authors could use to investigate the issue without needing access to the application.

  • DFS-based solution

    • Resolve trees with incoming constraint set

    • Track dependency on the incoming constraint set so that we can aggressively cache solutions?

      • How to do this? Tracking only on packages queried is easy, can we do better than that and actually cache based on the kind of query? If we get a new solution request with a wider constraint set but same packages, when can we cache?
    • Result needs to include some indication of what choices were made, so that when resulting constraints are rejected we can compute the new constraint set to solve with.

Things We Need

Data structure for maintaing a partial solution:

  • assignment of packages to versions or not-included (!= unassigned).
  • includes collected of constraints for all of those versions
  • includes merged collection of those constraints

supports efficient insertion & removal of new assignments.

Somehwere we also need to keep the set of constraints we have collected but not yet applied, as we work through packages. If we work through one package's dependencies one at a time this might be trivial and local.

Workspace Management

  • Load existing workspace.
  • Fetch missing dependencies from existing workspace.
  • Update the workspace.

Dependency Resolution Area Tasks

  1. "Toolchain-based build process"
  • This is a significant refactor / cleanup of Swift OSS's build process which will ultimately: o Allow us to test swift-test with our in-tree tests. o Make it easier to build/test SwiftPM with downloadable toolchains (increasing ease of development for ourselves and others). o Overall make our build/install process easier to understand, test, and debug.
  1. DONE: Land XCBuild's FSProxy in SwiftPM
  • This is core infrastructure for abstracting our file system access. o This will allow us to have efficient, focused tests for the convention derivation system. That will greatly reduce our testing time significantly. o This is also infrastructure I plan to use to develop non-filesystem based access to bare git repositories, used for efficient dependency resolution.

  • This is infrastructure we already have in XCBuild, I am porting it over and cleaning it up some as I go.

  1. DONE: Implement FSProxy-based access to Git repositories
  • Mentioned above, this will allow us to have elegant APIs for working with Git repository content (in particular, to quickly extract the Package.swift manifest from arbitrary tags).
  • This will also allow us to apply the convention system to bare git repos, which is useful infrastructure for SwiftPM-related tooling (index, etc)
  • In the long term, I hope to use this to execute builds entirely from the bare repository, which will give us very high performance and incredible correctness guarantees.
  1. DONE: Continue to develop CheckoutManager interfaces
  • This is the lowest level repository manager, which I have started but is not yet used and will need further APIs to be developed.
  1. DONE: Implement RepositoryDescriptionProvider interfaces
  • This is new infrastructure for abstracting out fetching the package descriptions from arbitrary versions from repositories managed by the CheckoutManager, and managing the caching of that information.
  • This layer will likely have a persistence component so that we can avoid recomputation of much of this information across program invocations.
  • This uses the infrastructure in #2 and #3.
  1. Additional random infrastructure
  • It is likely we will need a random grab bag of small pieces of infrastructure (Caches, concurrency, etc) for things above.
  1. DONE: Implement PackageDependencyResolver interfaces
  • This is the core version resolution algorithm.
  • This leverages #2, #3, and #4 heavily to be efficient, and should end up being a straightforward algorithm. This will not implement backtracking or any "fancy" solution to the full on NP-complete version resolution problem. My belief is that it will suffice for the current problem space.
  1. Implement WorkspaceManager interface
  • This is new infrastructure responsible for managing a working project directory.
  • This uses all of the infrastructure above to manage a persistent representation of the project/repository state, compute the desired state of the project, and reconcile that with the active state.
  1. Implement --update
  • This should be a small change on top of the infrastructure above.
  1. Implement --edit
  • This should be a smallish amount of work on top of the infrastructure above.
  • This will implement the persistence of the editable state, extending the WorkspaceManager to reconcile that state, and diagnostics.
  1. Implement PackageGraph module
  • This is new infrastructure to have a single place which builds the composed package graph and annotates it with all of the semantic information needed to build correctly (currently much of this is intertwined with the build process).
  • This involves defining abstract concepts for common operations like the desired deployment target of a module.
  1. Clean up build manifest
  • Ensure we produce one artifact per target (static library or dylib, and most likely switch to an explicit dylib model)
  • Audit the dependencies in the manifest (for which I know there are bugs)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.