mirror of
https://github.com/semver/semver.git
synced 2026-07-11 03:53:53 -05:00
[GH-ISSUE #970] Clarifying Lexical Comparison for Identifier Precedence (Again) #5716
No Assignees
Notifications
Due Date
No due date set.
Dependencies
No dependencies set.
Reference: github-starred/semver#5716
Reference in New Issue
Block a user
Delete Branch "%!s()"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
Originally created by @BenjaminHolland on GitHub (Aug 31, 2023).
Original GitHub issue: https://github.com/semver/semver/issues/970
I've looked at #832 and #561, and I'm still not sure how to resolve a comparison like
1.0.0-alpha.1
1.0.0-1.alpha
Is it safe to assume that the comparison here will be alphanumeric, even though one field in each comparison is numeric?
@hoelzeli commented on GitHub (Sep 3, 2023):
I think so, yes. 11.4 is the relevant section:
So the prerelease version will be split into the identifiers like so (written as python arrays and python strings):
1.0.0-alpha.1 --> prerelease identifiers: ["alpha", 1]
1.0.0-1.alpha --> prerelease identifiers: [1, "alpha"]
The comparisons would therefore be:
The second comparison will never be reached because "alpha" takes precedence over 1 (section 11.4.3)
@jwdonahue commented on GitHub (Sep 14, 2023):
So first we have #9:
Then there's #11:
Fortunately, the ASCII codes for the digits [0..9] are lower than the codes for [a..z] and [A..Z], so as long as your string consists of ASCII or UTF-8 characters in those character ranges, you can simply compare each character of each field from left to right until you encounter a character that is greater, or the field has more characters. So:
'a' > '1' (ie; 97 > 49), and your done.
So there's no need to ever convert a numeric identifier to a scaler like int or long, it's just wasteful.
I do always split the string on the dots and make sure the first three fields are pure numeric characters and the remaining fields are in the expected character ranges, before doing any comparisons. While not explicitly stated in the spec, the SemVer rules do not apply to non-SemVer strings. Such comparisons require consideration of implicit and explicit semantics, if any, of the non-SemVer string and may also require attention to cultures.
See also:
@kleindaniel81 commented on GitHub (Jul 28, 2024):
Really? Just to be sure, this only applies if both identifiers are compared lexically, right? You must still convert to numeric if both identifiers are numeric because comparing lexically, e.g., '10' < '2'.
Edit:
Ah, now I see. I missed the details:
So we have '1' < '2'. But then there is a second character, '0', in the first field and none in the second. Since a longer string has higher precedence, comparing character-by-character, ['1','0'] > ['2',''].
@jwdonahue commented on GitHub (Jul 28, 2024):
@kleindaniel81 Ya, just watch for the special case where you have something like "1A" and "1", which is the only case where the shorter string wins, because it is pure numeric. SemVer rules allow for a single pass over both strings, to determine there relative order, without any conversions from string to int, and that is the only correct algorithm for all possible valid SemVer strings, since some legal strings, may consist of numeric fields that are much larger than int or any scalar value that some languages are capable of representing.
@kleindaniel81 commented on GitHub (Jul 28, 2024):
@jwdonahue I don't think '1A' has higher precedence than (numeric) 1. From
I understand that when you compare a purely numeric identifier to a non-numeric one, the latter has higher precedence.
You make a good point about (ridiculously) large numeric identifiers.
Edit:
OK, this stuff is indeed a bit complicated. I needed some time to process the information. So comparing "1A" to "1" should not be problematic because there is no difference between "1" and "1". Then there is an additional "A" making the first string longer than the second, hence it has higher precedence. Depending on implementation details, I think the problem is comparing e.g. "1A" to "2". Because "1" < "2" (conversely "2" > "1") we find the first difference already in the first character. An algorithm might stop here and incorrectly conclude that "1A" < "2". So while there is no need to convert to numeric (and indeed large numbers may break the algorithm), there is certainly a need to classify the compared identifiers into 'numeric' and 'non-numeric'.
IMHO the SemVer specifications would benefit from being more explicit about comparing non-numeric identifiers to numeric ones. Something along the lines:
This is assuming, of course, that my interpretation of the respective section is correct.
@RobSmyth commented on GitHub (Oct 15, 2024):
That does not seem quite right to me. The spec talks about identifiers not characters within an identifier. So I take "1A" as non-numeric and "2" as numeric. So the spec
When comparing numeric to non-numeric identifiers, numeric identifiers always have lower precedence than non-numeric identifiersmeans that1Ahas higher precedence to both1and2. String-character comparison does not apply.Me too ... hence my post. Important to me as it impacts how I design versioning for my projects.
@kleindaniel81 commented on GitHub (Oct 15, 2024):
@RobSmyth Yes, your interpretation is correct. There is no doubt about that.
We might have gone off-topic here discussing algorithm implementation details. More specifically, the idea is to compare two version strings in a single pass, meaning character by character. Generally, the order of ASCII codes allows for characterwise comparisons because the codes for the set [0-9] are lower than for the set of non-digits [A-Za-z]. Still, you have to watch out for numeric to alpha-numeric comparisons. @jwdonahue has an excellent algorithm that does that.
Now, you don't have to do the comparisons in a single pass. You must, however, not convert string characters to numeric. Even if both fields are numeric, they must be compared lexically, because SemVer specs place no restrictions on numeric fields while programming languages cannot represent infinitely large numbers.
@jwdonahue commented on GitHub (Oct 15, 2024):
@kleindaniel81 @RobSmyth
It's been a few years since I wrote that code and I wound up taking a contract, that erased my brain.
I think I walk the version string 1 character at a time, building a record of metadata over each field, that classifies every field as either numeric or alpha numeric and whether it's major, minor, patch, or part of a prerelease or build meta tag, and how long it is. If at any time, one of the rules is broken, it's marked as non-semver.
After that pass, I can confidently compare two version strings, via that meta data. A pair of major fields with different lengths is easy to sort, but if they are the same length, then I compare them in appropriately sized blocks, treating groups of 8 bit chars, as if they were an unsigned uint_8/16/32/64 as appropriate for their size. I wrote a set of macro's that effectively wash-out big/little endian issues.
So if I have a pair fields to compare, "AA" and "24", the metadata tells me one is alpha and the other numeric, the rules allow me to sort them without further analysis. If I have "123" and "45", I already know they are numeric, and the length is the deciding factor. If they are "12" and "45", I use the appropriate macro to compare them as a pair of 16 bit unsigned integers, 0x3132 and 0x3435. I am sure it's slightly more complicated than that, but that's the gist of it.
One reason I did it that way, was to convert the semver string into a record, that could then be stored/reused, so that comparisons between those records, was single pass and faster than working the raw string. I haven't looked at the code in a while, but I think I may have avoided copying, by preserving the string and adding meta that references into it.
The code is quite complex and incomplete, in that it doesn't do the storage and retrieval bits that I had intended. I never got back to it, because I had gotten to the point where I needed a valid set of oracles to test against. Pretty sure I didn't set it aside, before ensuring that it passed the limited set of oracles, posted on some other threads in this issue base (look for discussions about the regex's in the FAQ).
The motivation came from an analysis of large real-world data sets, that gave me the frequencies of various lengths and numbers of fields that were being stored and eventually compared. I still need to test whether the extra meta data storage is required for reasonable speed gains in doing comparisons. I am pretty sure, that extra storage buys a big speed-up when sorting.
I think it was some interactions with the crate guys, that got me on that tangent.
@RobSmyth commented on GitHub (Oct 16, 2024):
Thx ... now I get it. Your focused on performance and my application works as part of a UI on one local semver at a time so anything less that 10ms is just fine for me. I was wondering why not just split the string into identifiers and then use the programming language to check if numeric. But I get it now.
Thank you.
@jwdonahue commented on GitHub (Oct 16, 2024):
@RobSmyth Oh, ya, I've done it the slow, very readable/maintainable way, many many times, in several languages. That's how I learned that users will adopt and then abuse any tool you hand them.
One of my early bugs had to do with a CI/CD system that burned through thousands of patch numbers per day, until my tool started throwing exceptions after a few months. That's also when I first started telling people that SemVer isn't always the right choice.