# Blueprint resolution

## Version specification

Users can specify a full [semver](https://):

`1.0.0`
`1.0.0-alpha1`
`1.0.0-alpha1+foo`

Or they can specify a `+` in the minor or patch positions:

`2.+`
`2.1.+`

Crucially, `+` means we will fetch the *latest* such version --- even if that version has dependencies that conflict with other requirements and thus causes a failure. In other words, specifying `2.+` does *not* mean "pick the latest version `2.x` *that is also compatible with everything else*."[^greedy]

## The dep res algo

Traverse the graph [using DFS with "backtracking"](https://stackoverflow.com/a/53995651/5175433). This makes it easy to find cycles. Keep track of two sets of "visited" nodes: those that are in the *current* DFS path (which get popped at the end of the recursive method, i.e. backtracked), and those that have *ever* been visited (so that work isn't duplicated).

Keep a map of (G, A) => V (initially empty). On each occurrence of a (G, A), the V should either be new or else match the existing V. In case of `+` in the given V, query for the latest V and use that. Pretty straightforward.

Also keep a map of (G, A) => {paths that reach it, with the versions they requested (and what each version resolved to)}. E.g.:

 (G1, A4) => {
   (G1, A1) -> (G1, A5) -> (G1, A2) -> (G1, A4): 1.1.+ (=1.1.5)
   (G1, A1) -> (G1, A3) -> (G1, A4): 1.+ (=1.1.5)
   (G1, A1) -> (G1, A4): 1.1.4
 }

Instead of failing fast, fail at the end of resolution. That way, users can see all failures.

*TODO*: Find a prettier way to print those failures.

[^greedy]:
If users expect `x.+` to mean "the latest minor version in `x` that is consistent with other constraints" but we try to resolve it by only trying the *latest* minor version in `x`, then resolution may fail unexpectedly: the latest may have incompatibilities that earlier minors did not. At first glance it's hard to fix this without an exponential search (iterating over all possible matches at each node in the DAG in descending order).

On the other hand, if we tell users that `+` means that we will always pick the *latest*, then this problem is mitigated. Two blueprints specifying `1.+` for some artifact will always be compatible, even though another specifying (say) `1.3.+` will cause the set to start failing once `1.4.0` is published. This seems like a fine tradeoff.