Version requirements: caret, tilde, wildcard, pre-releases

A dependency line in Cargo.toml, such as serde = "1.0.200", is a version requirement: a rule that says which published versions of the crate are acceptable. Cargo picks a version that satisfies the rule. In this problem you implement that rule check for a defined subset of the syntax, plus a function that picks the best candidate from a list.

pub fn matches(req: &str, version: &str) -> bool
pub fn select(req: &str, available: Vec<String>) -> Option<String>

matches answers "does this version satisfy this requirement?". select returns the highest version in available that satisfies the requirement, or None if none does.

Terms

A version has three numbers, major.minor.patch, such as 1.4.2. It may carry a pre-release tag after a hyphen, as in 1.0.0-alpha.2, which marks a test build published before 1.0.0. A requirement is made of one or more comparators, such as ^1.2 or <1.5, separated by commas. A comparator may be partial: it may leave out the patch field, or both the minor and patch fields (1.2 or 1).

The rules below follow the Cargo reference and the semver crate, which Cargo uses to parse and match requirements.

Caret: the default operator

A comparator with no operator is a caret comparator, so foo = "1.2.3" in a manifest means ^1.2.3. A caret allows any version at or above the one written that does not change the leftmost non-zero field among the fields you wrote. If every written field is zero, the last written field is the one that may not change.

requirement	range
`^1.2.3`	`>=1.2.3, <2.0.0`
`^1.2`	`>=1.2.0, <2.0.0`
`^1`	`>=1.0.0, <2.0.0`
`^0.2.3`	`>=0.2.3, <0.3.0`
`^0.2`	`>=0.2.0, <0.3.0`
`^0.0.3`	`>=0.0.3, <0.0.4`
`^0.0`	`>=0.0.0, <0.1.0`
`^0`	`>=0.0.0, <1.0.0`

The rows starting with 0 are the ones to read carefully. For ^0.2.3 the leftmost non-zero field is the minor field, so 0.3.0 is outside the range: Cargo treats 0.2.x and 0.3.x as incompatible. cargo update therefore never moves a 0.2 requirement to 0.3.0; the requirement in Cargo.toml has to be changed. For ^0.0.3 the only allowed version is 0.0.3 itself. Its pre-releases, such as 0.0.3-alpha, sort below 0.0.3 and so are outside the range.

Tilde: keep the major and minor fields

A tilde comparator keeps the major and minor fields if you wrote the minor field. If you wrote only the major field, it keeps the major field.

requirement	range
`~1.2.3`	`>=1.2.3, <1.3.0`
`~1.2`	`>=1.2.0, <1.3.0`
`~1`	`>=1.0.0, <2.0.0`

So ~1 has the same range as ^1, while ~1.0 stops at 1.1.0. Whether a field was written matters, which is why your parser must remember it.

Wildcards

* alone matches every release version. (The Cargo reference notes that crates.io does not accept a bare * requirement in a published crate.) 1.* means >=1.0.0, <2.0.0, and 1.2.* means >=1.2.0, <1.3.0. Note that 1.2.* is not the same as ^1.2: 1.5.0 matches ^1.2 but not 1.2.*.

Comparison operators

=, >, >=, < and <= compare in the usual way when all three fields are written. With a partial operand, the operand stands for the whole group of versions that start with the written fields:

requirement	range
`=1.2`	`>=1.2.0, <1.3.0`
`=1`	`>=1.0.0, <2.0.0`
`>1.2`	`>=1.3.0` (past every `1.2.x`)
`>=1.2`	`>=1.2.0`
`<1.2`	`<1.2.0`
`<=1.2`	`<1.3.0` (up to and including every `1.2.x`)

Commas mean and: >=1.2, <1.5 is satisfied only by versions that satisfy both comparators, so 1.4.9 matches and 1.5.0 does not.

Pre-releases

Ordering. A pre-release sorts below the release with the same three numbers: 1.0.0-alpha < 1.0.0. Two pre-release tags on the same numbers are compared field by field, where fields are the parts between dots:

two fields made only of digits compare as numbers, so alpha.2 < alpha.11 (as text, "11" would sort before "2");
other fields compare as text in ASCII order (alpha < beta);
a digits-only field sorts below a field containing any other character (1 < alpha);
if one tag is a prefix of the other, the shorter one is lower (alpha < alpha.1).

Admission. Satisfying every comparator is not enough for a pre-release. A pre-release version matches only if, in addition, at least one comparator in the requirement has a pre-release tag and the same major.minor.patch as the version. So ^1.0 does not match 1.2.0-beta.1, * matches no pre-release, and >=1.0.0-alpha.2, <1.0.0 matches 1.0.0-alpha.11. The admission rule only adds a condition: ^1.0.0-alpha still matches the release 1.0.0, because releases need no admission.

Contract

A version argument is exactly major.minor.patch, optionally followed by - and a pre-release tag, optionally followed by + and build metadata. Build metadata is ignored for ordering and matching.
A requirement is one or more comparators separated by commas, with optional spaces around each comparator. A comparator is *; or M.* or M.m.*; or an optional operator (^, ~, =, >, >=, <, <=) followed by M, M.m or M.m.p. A pre-release tag may follow a full M.m.p.
Every number is a decimal u64 without leading zeros, and can be as large as u64::MAX, so computing "one more than the major field" must not overflow. Pre-release fields are non-empty and contain only ASCII letters, digits and hyphens.
The tests use only inputs in this grammar. Other forms that Cargo accepts, such as 1.x, are not tested; you may return false for anything you do not parse, but you must not panic.
select compares versions with the ordering above and returns the original string of the highest matching entry. It skips entries that are not valid versions. If several matching entries are equal versions, it returns the first of them. An empty list gives None.