Diffing package sets with nvd-json

Versions

The first thing we need is a datatype to represent the version of a package. Versions are strings, but we don't just want to treat them as strings. A version string is better compared by splitting up the individual components, ignoring separators, and then comparing those, possibly numerically. So let's introduce an enum for each chunk of a version.

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum VersionChunk {
    Int(u64),
    Str(String),
}

A version chunk is either an integer or a string. Any chunk of a version string that is all digits will be treated as an integer. Otherwise it will be treated as a string. Now we need to implement the logic for comparing these chunks, since that will be the building block for comparing entire versions.

use std::cmp::Ordering;

impl Ord for VersionChunk {
    fn cmp(&self, other: &Self) -> Ordering {
        match (self, other) {
            <<version-chunk-rules>>
        }
    }
}

impl PartialOrd for VersionChunk {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

A VersionChunk can be totally ordered, so we implement the Ord trait for, and implement PartialOrd in terms of that. We'll go through the individual match cases in more detail, since they're a big confusing.

(left, right) if left == right => Ordering::Equal,

Of course, the first case is simple: if the two chunks are the same, they compare as equal.

(VersionChunk::Int(left), VersionChunk::Int(right)) => left.cmp(right),

If both chunks are integers, then compare the integers and use that as the result. Note that we don't have a case like this for strings just yet, as there is a special case that needs to be considered first.

(VersionChunk::Str(val), _) if val == "pre" => Ordering::Less,
(_, VersionChunk::Str(val)) if val == "pre" => Ordering::Greater,

A chunk with the string "pre" is treated special, as it generally indicates a prerelease version. Because of that, it compares as less than any other chunk.

(VersionChunk::Str(left), VersionChunk::Str(right)) => left.cmp(right),

With prereleases out of the way, we can straightforwardly compare two string chunks lexicographically.

(VersionChunk::Int(_), VersionChunk::Str(_)) => Ordering::Greater,
(VersionChunk::Str(_), VersionChunk::Int(_)) => Ordering::Less,

Finally, we need to define how integer chunks compare with string chunks. We choose to treat a string as less than an integer, because they usually consistute labels like "alpha" or "beta", so they should come before a real version number.

With the logic defined for version chunks, we can define a type to represent the version of a package.

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct Version {
    pub text: String,
    pub chunks: Vec<VersionChunk>,
}

A Version contains a list of version chunks parsed out a string, and it keeps a copy of the string it originally came from. This is because as we'll see soon, parsing the string into chunks discards some information, so it is useful to still be able to print the version as it was originally written.

The next thing we'll need is a way to create a Version from a string, parsing the text into chunks.

impl Version {
    pub fn new(text: &str) -> Self {
        let mut iter = text.chars().peekable();
        let mut chunks = Vec::new();

        while let Some(next) = iter.next() {
            <<version-parse-char>>
        }

        Self {
            text: text.to_string(),
            chunks,
        }
    }
}

Parsing a version string into chunks involves iterating over the characters of the string. We use a peekable iterator because we will want to be able to consume characters as long as they meet certain conditions, and once they don't, leave them for the next chunk. So the peek() method on the iterator will let us do that.

The iteration will build up a list of chunks as it goes, and then afterwards we'll return a new Version with those chunks and a copy of the original string.

So now let's look at what we do in each iteration of the loop.

if next.is_ascii_digit() {
    <<version-parse-digit>>
} else if next.is_alphabetic() {
    <<version-parse-letter>>
}

Each run through the loop is going to add at most one chunk to the list. That chunk will either be an integer or string chunk depending on whether the next character is a digit or alphabetical character. If it's some other kind of character, it will be ignored and the loop will continue to the next character without producing a chunk. This is why parsing a version into chunks is lossy: non-alphanumeric characters are discarded and not considered when comparing versions.

Now let's see how we parse an integer chunk.

let mut chunk = String::new();
chunk.push(next);

while iter.peek().is_some_and(char::is_ascii_digit) {
    chunk.push(iter.next().unwrap());
}

let val: u64 = chunk.parse().unwrap();
chunks.push(VersionChunk::Int(val));

We create a string that we will push characters into to form the full set of digits for this chunk, and immediately push the current character. Then we keep popping off characters from the iterator as long as they continue to be digits, and append them to the string for the chunk. Finally, when we've either run out of digit characters, we parse what we've collected into an integer and add that as a chunk to the list. We're unwrapping the error from parsing because we know we're only adding digits to the string, so it should parse successfully as a u64. Perhaps this should be revisited, as it's possible there could be too many digits to fit in a u64. One possible way to handle that would be to fallback to a string chunk in that case.

Parsing a string chunk is pretty similar.

let mut chunk = String::new();
chunk.push(next);

while iter.peek().is_some_and(|c| c.is_alphabetic()) {
    chunk.push(iter.next().unwrap());
}

chunks.push(VersionChunk::Str(chunk));

This looks almost identical to the code for parsing integer chunks, so there's probably some code that could be extracted into a common function. The main difference is that we don't have to parse the string: we can just create the chunk from the string we've built up of letters.

n.b. Currently, this logic splits chunks anywhere we switch from digits to letters or vice versa. So for instance, "1.2.3beta4" has chunks for 1, 2, 3, "beta", and 4. This makes sense in this case, but trips a bit on things like Git revisions, which can often find their way into versions as well. Something like "c2656d98" is semantically a single string chunk of a version, but it splits into four separate chunks. Getting the former right is probably more important than the latter, so that's why this remains as-is.

That's all there really is to versions. They're a simple abstraction to make comparison of versions easier. You may notice a lot of edge cases that aren't handled around parsing the chunks or how they are ordered. For my purposes, this is fine. In most cases, equality of versions is all that matters for diffing. Ordering generally just needs to be somewhat reasonable and coherent for presentation purposes.

Packages

With versions done, let's continue upwards to packages. A package is constructed from a Nix store path. Upon construction, we'll look at the basename of the path and split the name portion into a pname and version. So we'll start by creating a type that holds those pieces as well as the original store path.

use std::path::{Path, PathBuf};

#[derive(Debug, PartialEq, Eq)]
pub struct Package {
    pub pname: String,
    pub version: Version,
    pub store_path: PathBuf,
}

Now we need a function to create a package from a store path.

impl Package {
    pub fn from_store_path(path: &Path) -> Option<Self> {
        <<package-from-store-path>>
    }
}

Creating a package from a path can fail, particularly for weird paths like "/" that should hopefully never come up. But because it's possible, we'll return an Option. Now let's dig in to the actual implementation.

let basename = path.file_name()?.to_str()?;
let chunks: Vec<&str> = basename.split('-').skip(1).collect();

We take the basename of the path (the rest is not important) and split it into chunks separated by dashes. Remember that a Nix store path will look something like:

/nix/store/0dnf7dm4lj3vn3y5bf0ayzkd1nh9wpvd-drkonqi-6.2.90

For our purposes we don't care about the dirname or the hash at the start of the basename, so we skip the first dash-separated component, and collect the rest into a list of strings.

let (pname_chunks, version_chunks) = match chunks.iter().position(|chunk| {
    if let Some(c) = chunk.chars().nth(0) {
        c.is_ascii_digit()
            || (chunk.len() >= 7 && chunk.chars().all(|c| c.is_ascii_hexdigit()))
    } else {
        false
    }
}) {
    Some(pos) => chunks.split_at(pos),
    None => (&chunks[..], &[] as &[&str]),
};

The goal here is to find where the pname ends and the version starts. While in Nix code these are usually specified explicitly as separate attributes, in the store path they are just separated by a dash. And because both the pname and version may contains dashes themselves, it's not always obvious where the version actually begins.

So we'll use a heuristic to decide where we think the version starts. The simplest method would be to treat the first chunk that starts with a number as the beginning of the version. That mostly works well, but once again Git revisions conspire to make things difficult.

The core of the problem is that when the version is just a Git revision, which are made up of hexadecimal characters, it may or may not start with a digit. If it does, then the version gets split up correctly, but if it happens to start with a letter, then the revision ends up parsed as part of the pname instead, leading to very confusing diff results when packages get matched up by pname.

To fix this, in addition to chunks that start with digits, we also consider the version to start with a chunk that is at least 7 characters long (conventional for short versions of Git revisions) and contains exclusively hexadecimal characters. In theory, this might allow for some false positives: for instance, a package called "foo-deadbeef" would interpret "deadbeef" as a version. In practice, I haven't seen this be an issue.

Once we've found which chunk begins the version of the package, we split the chunks into two slices at that position.

let pname = pname_chunks.join("-");
let version = version_chunks.join("-");

Some(Package {
    pname,
    version: Version::new(&version),
    store_path: path.to_path_buf(),
})

With the pname and version chunks separated, we can join them back together with dashes and construct the final package.

mod tests;

<<imports>>

<<version-chunk>>

<<version>>

<<package>>