I was doing some research into how RPM compares versions, as it appeared to be more complex than simple semver comparisons. Turns out is super whacky. One of the Puppet authors wrote a blog post to much better explain what’s going on. I’m going to just copy it here so I have my own copy in case the blog ever goes away.
Package Naming and Parsing
RPM package names are made up of five parts; the package name, epoch, version, release, and architecture. This format is commonly referred to as the acronym NEVRA. The epoch is not always included; it is assumed to be zero (0) on any packages that lack it explicitly. The format for the whole string is n-e:v-r.a
. For my purposes, I was only really concerned with comparing theEVR portion; Puppet knows about package names and the bug herein was with what Puppet calls the “version” (EVR in yum/rpm parlance). Parsing is pretty simple:
- If there is a
:
in the string, everything before it is the epoch. If not, the epoch is zero. - If there is a
-
in the remaining string, everything before the first-
is the version, and everything after it is the release. If there isn’t one, the release is considered null/nill/None/whatever.
How Yum Compares EVR
Once the package string is parsed into its EVR components, yum calls rpmUtils.miscutils.compareEVR()
, which does some data type massaging for the inputs, and then calls out to rpm.labelCompare()
(found in rpm.git/python/header-py.c
).labelCompare()
sets each epoch to “0” if it was null/Nonem, and then uses compare_values()
to compare each EVR portion, which in turn falls through to a function called rpmvercmp()
(see below). The algorithm for labelCompare()
is as follows:
- Set each epoch value to 0 if it’s null/None.
- Compare the epoch values using
compare_values()
. If they’re not equal, return that result, else move on to the next portion (version). The logic withincompare_values()
is that if one is empty/null and the other is not, the non-empty one is greater, and that ends the comparison. If neither of them is empty/not present, compare them usingrpmvercmp()
and follow the same logic; if one is “greater” (newer) than the other, that’s the end result of the comparison. Otherwise, move on to the next component (version). - Compare the versions using the same logic.
- Compare the releases using the same logic.
- If all of the components are “equal”, the packages are the same.
The real magic, obviously, happens in rpmvercmp()
, the rpm library function to compare two versions (or epochs, or releases). That’s also where the madness happens.
How RPM Compares Version Parts
RPM is written in C. Converting all of the buffer and pointer processing for these strings over to Ruby was quite a pain. That being said, I didn’t make this up, this is actually the algorithm that rpmvercmp()
(lib/rpmvercmp.c
) uses to compare version “parts” (epoch, version, release). This function returns 0 if the strings are equal, 1 if a
(the first string argument) is newer than b
(the second string argument), or -1 if a
is older than b
. Also keep in mind that this uses pointers in C, so it works by removing a sequence of 0 or more characters from the front of each string, comparing them, and then repeating for the remaining characters in each string until something is unequal, or a string reaches its end.
- If the strings are binary equal (
a == b
), they’re equal, return 0. - Loop over the strings, left-to-right.
- Trim anything that’s not
[A-Za-z0-9]
or tilde (~
) from the front of both strings. - If both strings start with a tilde, discard it and move on to the next character.
- If string
a
starts with a tilde and stringb
does not, return -1 (stringa
is older); and the inverse if stringb
starts with a tilde and stringa
does not. - End the loop if either string has reached zero length.
- If the first character of
a
is a digit, pop the leading chunk of continuous digits from each string (which may be ” forb
if only onea
starts with digits). Ifa
begins with a letter, do the same for leading letters. - If the segement from
b
had 0 length, return 1 if the segment froma
was numeric, or -1 if it was alphabetic. The logical result of this is that ifa
begins with numbers andb
does not,a
is newer (return 1). Ifa
begins with letters andb
does not, thena
is older (return -1). If the leading character(s) froma
andb
were both numbers or both letters, continue on. - If the leading segments were both numeric, discard any leading zeros and whichever one is longer wins. If
a
is longer thanb
(without leading zeroes), return 1, and vice-versa. If they’re of the same length, continue on. - Compare the leading segments with
strcmp()
(or<=>
in Ruby). If that returns a non-zero value, then return that value. Else continue to the next iteration of the loop.
- Trim anything that’s not
- If the loop ended (nothing has been returned yet, either both strings are totally the same or they’re the same up to the end of one of them, like with “1.2.3” and “1.2.3b”), then the longest wins – if what’s left of
a
is longer than what’s left ofb
, return 1. Vice-versa for if what’s left ofb
is longer than what’s left ofa
. And finally, if what’s left of them is the same length, return 0.
I also found a GitHub repo for a pure Python implementation of this, instead of loading in the C library to python. Here is the main code (again, just copying to make sure I have my own copy)
# # Copyright (c) SAS Institute Inc. # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # http://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. # from __future__ import print_function from __future__ import unicode_literals import re class Vercmp(object): R_NONALNUMTILDE = re.compile(br"^([^a-zA-Z0-9~]*)(.*)$") R_NUM = re.compile(br"^([\d]+)(.*)$") R_ALPHA = re.compile(br"^([a-zA-Z]+)(.*)$") @classmethod def compare(cls, first, second): first = first.encode("ascii", "ignore") second = second.encode("ascii", "ignore") while first or second: m1 = cls.R_NONALNUMTILDE.match(first) m2 = cls.R_NONALNUMTILDE.match(second) m1_head, first = m1.group(1), m1.group(2) m2_head, second = m2.group(1), m2.group(2) if m1_head or m2_head: # Ignore junk at the beginning continue # handle the tilde separator, it sorts before everything else if first.startswith(b'~'): if not second.startswith(b'~'): return -1 first, second = first[1:], second[1:] continue if second.startswith(b'~'): return 1 # If we ran to the end of either, we are finished with the loop if not first or not second: break # grab first completely alpha or completely numeric segment m1 = cls.R_NUM.match(first) if m1: m2 = cls.R_NUM.match(second) if not m2: # numeric segments are always newer than alpha segments return 1 isnum = True else: m1 = cls.R_ALPHA.match(first) m2 = cls.R_ALPHA.match(second) isnum = False if not m1: # this cannot happen, as we previously tested to make sure that # the first string has a non-null segment return -1 # arbitrary if not m2: return 1 if isnum else -1 m1_head, first = m1.group(1), m1.group(2) m2_head, second = m2.group(1), m2.group(2) if isnum: # throw away any leading zeros - it's a number, right? m1_head = m1_head.lstrip(b'0') m2_head = m2_head.lstrip(b'0') # whichever number has more digits wins m1hlen = len(m1_head) m2hlen = len(m2_head) if m1hlen < m2hlen: return -1 if m1hlen > m2hlen: return 1 # Same number of chars if m1_head < m2_head: return -1 if m1_head > m2_head: return 1 # Both segments equal continue m1len = len(first) m2len = len(second) if m1len == m2len == 0: return 0 if m1len != 0: return 1 return -1 def vercmp(first, second): return Vercmp.compare(first, second)