docs/BLS: describe version comparisons

Fixes #23346.

1 files changed, 114 insertions, 10 deletions

diff --git a/docs/BOOT_LOADER_SPECIFICATION.md b/docs/BOOT_LOADER_SPECIFICATION.md
index 4ab66b6f6e..d489208542 100644
--- a/docs/BOOT_LOADER_SPECIFICATION.md
+++ b/docs/BOOT_LOADER_SPECIFICATION.md
@@ -173,11 +173,12 @@ The following keys are recognized:
 
 * `version` is a human-readable version for this menu item. This is usually the
   kernel version and is intended for use by OSes to install multiple kernel
-  versions with the same `title` field. This field shall be in a syntax that is
-  useful for Debian-style version sorts, so that the boot loader UI can
-  determine the newest version easily and show it first or preselect it
+  versions with the same `title` field. This field is used for sorting entries,
+  so that the boot loader can order entries by age or select the newest one
   automatically. This field is optional.
 
+  See [Sorting](#sorting) below.
+
   Example: `version 3.7.2-201.fc18.x86_64`
 
 * `machine-id` is the machine ID of the OS. This can be used by boot loaders
@@ -192,13 +193,7 @@ The following keys are recognized:
 * `sort-key` is a short string used for sorting entries on display. This should
   typically be initialized from the `IMAGE_ID=` or `ID=` fields of
   [os-release](https://www.freedesktop.org/software/systemd/man/os-release.html),
-  possibly with an additional suffix. This field is optional. If set, it is
-  used as primary sorting key for the entries on display (lexicographically
-  increasing). It does not have to be unique (and usually is not). If
-  non-unique the the `machine-id` (lexicographically increasing) and `version`
-  (lexicographically decreasing, i.e. newest version first) fields described
-  above are used as secondary/ternary sorting keys. If this field is not set
-  entries are typically sorted by the `.conf` file name of the entry.
+  possibly with an additional suffix. This field is optional.
 
   Example: `sort-key fedora`
 
@@ -393,6 +388,100 @@ creating a partition and file system for it) and creates the `/loader/entries/`
 directory in it. It then installs an appropriate boot loader that can read
 these snippets. Finally, it installs one or more kernel packages.
 
+## Sorting
+
+The boot loader menu should generally show entries in some order meaningful to
+the user. The `title` key is free-form and not suitable to be used as the
+primary sorting key. Instead, the boot loader should use the following rules:
+if `sort-key` is set on both entries, use in order of priority,
+the `sort-key` (A-Z, increasing [alphanumerical order](#alphanumerical-order)),
+`machine-id` (A-Z, increasing alphanumerical order),
+and `version` keys (decreasing [version order](#version-order)).
+If `sort-key` is set on one entry, it sorts earlier.
+At the end, if necessary, when `sort-key` is not set or those fields are not
+set or are all equal, the boot loader should sort using the file name of the
+entry (decreasing version sort), with the suffix removed.
+
+**Note:** _This description assumes that the boot loader shows entries in a
+traditional menu, with newest and "best" entries at the top, thus entries with
+a higher version number are sorter *earlier*. The boot loader is free to
+use a different direction (or none at all) during display._
+
+### Alphanumerical order
+
+Free-form strings and machine IDs should be compared using a method equivalent
+to [strcmp(3)](https://man7.org/linux/man-pages/man3/strcmp.3.html) on their
+UTF-8 represenations. If just one of the strings is unspecified or empty, it
+compares lower. If both strings are unspecified or empty, they compare equal.
+
+### Version order
+
+The following method should be used to compare version strings. The algorithm
+is based on rpm's `rpmvercmp()`, but not identical.
+
+ASCII letters (`a-z`, `A-Z`) and digits (`0-9`) form alphanumerical components of the version.
+Minus (`-`) separates the version and release parts.
+Dot (`.`) separates parts of version or release.
+Tilde (`~`) is a prefix that always compares lower.
+Caret (`^`) is a prefix that always compares higher.
+
+Both strings are compared from the beginning until the end, or until the
+strings are found to compare as different. In a loop:
+1. Any characters which are outside of the set of listed above (`a-z`, `A-Z`, `0-9`, `-`, `.`, `~`, `^`)
+   are skipped in both strings. In particular, this means that non-ASCII characters
+   that are Unicode digits or letters are skipped too.
+2. If one of the strings has ended: if the other string hasn't, the string that
+   has remaining characters compares higher. Otherwise, the strings compare
+   equal.
+3. If the remaining part of one of strings starts with `~`:
+   if other remaining part does not start with `~`,
+   the string with `~` compares lower. Otherwise, both tilde characters are skipped.
+4. The check from point 2. is repeated here.
+5. If the remaining part of one of strings starts with `-`:
+   if the other remaining part does not start with `-`,
+   the string with `-` compares lower. Otherwise, both minus characters are skipped.
+6. If the remaining part of one of strings starts with `^`:
+   if the other remaining part does not start with `^`,
+   the string with `^` compares higher. Otherwise, both caret characters are skipped.
+6. If the remaining part of one of strings starts with `.`:
+   if the other remaining part does not start with `.`,
+   the string with `.` compares lower. Otherwise, both dot characters are skipped.
+7. If either of the remaining parts starts with a digit, numerical prefixes are
+   compared numerically. Any leading zeroes are skipped.
+   The numerical prefixes (until the first non-digit character) are evaluated as numbers.
+   If one of the prefixes is empty, it evaluates as 0.
+   If the numbers are different, the string with the bigger number compares higher.
+   Otherwise, the comparison continues at the following characters at point 1.
+8. Leading alphabetical prefixes are compared alphabetically.
+   The substrings are compared letter-by-letter.
+   If both letters are the same, the comparison continues with the next letter.
+   Capital letters compare lower than lower-case letters (`A < a`).
+   When the end of one substring has been reached (a non-letter character or the end
+   of the whole string), if the other substring has remaining letters, it compares higher.
+   Otherwise, the comparison continues at the following characters at point 1.
+
+Examples (with '' meaning the empty string):
+
+* `11 == 11`
+* `systemd-123 == systemd-123`
+* `bar-123 < foo-123`
+* `123a > 123`
+* `123.a > 123`
+* `123.a < 123.b`
+* `123a > 123.a`
+* `11α == 11β`
+* `A < a`
+* '' < `0`
+* `0.` > `0`
+* `0.0` > `0`
+* `0` < `~`
+* '' < `~`
+
+Note: [systemd-analyze](https://www.freedesktop.org/software/systemd/man/systemd-analyze.html)
+implements this version comparison algorithm as
+```
+systemd-analyze compare-versions <version-a> <version-b>
+```
 
 ## Additional discussion
 
@@ -467,6 +556,21 @@ functionality, this specfication is still needed for the following reasons:
   useful if the OS UI has a standardized way to discover available boot options
   which can be booted to.
 
+### Why is the version comparsion logic so complicated?
+
+The `sort-key` allows us to group entries by "operating system", e.g. all
+versions of Fedora together, no matter if they identify themselves as "Fedora
+Workstation" or "Fedora Rawhide (prerelease)". The `sort-key` was introduced
+only recently, so we need to provide a meaningful order for entries both with
+and without it. Since it is a new concept, it is assumed that entries with
+`sort-key` are newer.
+
+In a traditional menu with entries displayed vertically, we want names to be
+sorter alpabetically (CentOS, Debian, Fedora, OpenSUSE, …), it would be strange
+to have them in reverse order. But when multiple kernels are available for the
+same installation, we want to display the latest kernel with highest priority,
+i.e. earlier in the list.
+
 ### Out of Focus
 
 There are a couple of items that are out of focus for this specification: