mail archive of the barebox mailing list
 help / color / mirror / Atom feed
From: Ahmad Fatoum <ahmad@a3f.at>
To: barebox@lists.infradead.org
Cc: Ahmad Fatoum <ahmad@a3f.at>
Subject: [PATCH 3/3] string: import strverscmp_improved from systemd
Date: Wed, 31 May 2023 08:28:53 +0200	[thread overview]
Message-ID: <20230531062853.670751-4-ahmad@a3f.at> (raw)
In-Reply-To: <20230531062853.670751-1-ahmad@a3f.at>

The Boot Loader specification now references the UAPI group's version
format specification[1] on how blspec entries should be sorted.

In preparation of aligning barebox entry sorting with the specification,
import systemd's strverscmp_improved as strverscmp and add some tests
for it.

The selftest is called string.c, because it indirectly tests some string
mangling function and in anticipation of adding more string tests in the
future.

[1]: https://uapi-group.org/specifications/specs/version_format_specification/#examples

Signed-off-by: Ahmad Fatoum <ahmad@a3f.at>
---
 include/string.h   |   2 +
 lib/Kconfig        |   9 ++-
 lib/Makefile       |   1 +
 lib/strverscmp.c   | 165 ++++++++++++++++++++++++++++++++++++++++++
 test/self/Kconfig  |   6 ++
 test/self/Makefile |   1 +
 test/self/string.c | 175 +++++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 358 insertions(+), 1 deletion(-)
 create mode 100644 lib/strverscmp.c
 create mode 100644 test/self/string.c

diff --git a/include/string.h b/include/string.h
index 499f2ec03c02..43911b75762f 100644
--- a/include/string.h
+++ b/include/string.h
@@ -18,4 +18,6 @@ void *__nokasan_default_memcpy(void * dest,const void *src,size_t count);
 
 char *parse_assignment(char *str);
 
+int strverscmp(const char *a, const char *b);
+
 #endif /* __STRING_H */
diff --git a/lib/Kconfig b/lib/Kconfig
index b8bc9d63d4f0..84d2a2573625 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -107,7 +107,7 @@ config IMAGE_SPARSE
 	bool
 
 config STMP_DEVICE
-	bool "STMP device support" if COMPILE_TEST
+	bool "STMP device support"
 
 config FSL_QE_FIRMWARE
 	select CRC32
@@ -167,6 +167,13 @@ config PROGRESS_NOTIFIER
 	  This is selected by boards that register a notifier to visualize
 	  progress, like blinking a LED during an update.
 
+config VERSION_CMP
+	bool "version comparison utilities" if COMPILE_TEST
+	help
+	  This is selected by code that needs to compare versions
+	  in a manner compatible with
+	    https://uapi-group.org/specifications/specs/version_format_specification
+
 config PRINTF_UUID
 	bool
 	default y if PRINTF_FULL
diff --git a/lib/Makefile b/lib/Makefile
index 38478625423b..185e6221fdd2 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -6,6 +6,7 @@ obj-pbl-y		+= ctype.o
 obj-y			+= rbtree.o
 obj-y			+= display_options.o
 obj-y			+= string.o
+obj-$(CONFIG_VERSION_CMP)	+= strverscmp.o
 obj-y			+= strtox.o
 obj-y			+= kstrtox.o
 obj-y			+= vsprintf.o
diff --git a/lib/strverscmp.c b/lib/strverscmp.c
new file mode 100644
index 000000000000..da2d284918e0
--- /dev/null
+++ b/lib/strverscmp.c
@@ -0,0 +1,165 @@
+/* SPDX-License-Identifier: LGPL-2.1-or-later */
+/*
+ * Code taken from systemd src/fundamental/string-util-fundamental.c
+ * NOTE: Semantics differ from glibc strverscmp (e.g. handling of ~rc1)
+ */
+
+#include <string.h>
+#include <linux/ctype.h>
+#include <linux/export.h>
+
+static bool is_valid_version_char(char a)
+{
+        return isdigit(a) || isalpha(a) || a == '~' ||
+		a == '-' || a == '^' || a == '.';
+}
+
+int strverscmp(const char *a, const char *b)
+{
+        /* This function is similar to strverscmp(3), but it treats '-' and '.' as separators.
+         *
+         * The logic is based on rpm's rpmvercmp(), but unlike rpmvercmp(), it distiguishes e.g.
+         * '123a' and '123.a', with '123a' being newer.
+         *
+         * It allows direct comparison of strings which contain both a version and a release; e.g.
+         * '247.2-3.1.fc33.x86_64' or '5.11.0-0.rc5.20210128git76c057c84d28.137.fc34'.
+         *
+         * The input string is split into segments. Each segment is numeric or alphabetic, and may be
+         * prefixed with the following:
+         *  '~' : used for pre-releases, a segment prefixed with this is the oldest,
+         *  '-' : used for the separator between version and release,
+         *  '^' : used for patched releases, a segment with this is newer than one with '-'.
+         *  '.' : used for point releases.
+         * Note that no prefix segment is the newest. All non-supported characters are dropped, and
+         * handled as a separator of segments, e.g., '123_a' is equivalent to '123a'.
+         *
+         * By using this, version strings can be sorted like following:
+         *  (older) 122.1
+         *     ^    123~rc1-1
+         *     |    123
+         *     |    123-a
+         *     |    123-a.1
+         *     |    123-1
+         *     |    123-1.1
+         *     |    123^post1
+         *     |    123.a-1
+         *     |    123.1-1
+         *     v    123a-1
+         *  (newer) 124-1
+         */
+
+        a = a ?: "";
+        b = b ?: "";
+
+        for (;;) {
+                const char *aa, *bb;
+                int r;
+
+                /* Drop leading invalid characters. */
+                while (*a != '\0' && !is_valid_version_char(*a))
+                        a++;
+                while (*b != '\0' && !is_valid_version_char(*b))
+                        b++;
+
+                /* Handle '~'. Used for pre-releases, e.g. 123~rc1, or 4.5~alpha1 */
+                if (*a == '~' || *b == '~') {
+                        /* The string prefixed with '~' is older. */
+                        r = compare3(*a != '~', *b != '~');
+                        if (r != 0)
+                                return r;
+
+                        /* Now both strings are prefixed with '~'. Compare remaining strings. */
+                        a++;
+                        b++;
+                }
+
+                /* If at least one string reaches the end, then longer is newer.
+                 * Note that except for '~' prefixed segments, a string which has more segments is newer.
+                 * So, this check must be after the '~' check. */
+                if (*a == '\0' || *b == '\0')
+                        return compare3(*a, *b);
+
+                /* Handle '-', which separates version and release, e.g 123.4-3.1.fc33.x86_64 */
+                if (*a == '-' || *b == '-') {
+                        /* The string prefixed with '-' is older (e.g., 123-9 vs 123.1-1) */
+                        r = compare3(*a != '-', *b != '-');
+                        if (r != 0)
+                                return r;
+
+                        a++;
+                        b++;
+                }
+
+                /* Handle '^'. Used for patched release. */
+                if (*a == '^' || *b == '^') {
+                        r = compare3(*a != '^', *b != '^');
+                        if (r != 0)
+                                return r;
+
+                        a++;
+                        b++;
+                }
+
+                /* Handle '.'. Used for point releases. */
+                if (*a == '.' || *b == '.') {
+                        r = compare3(*a != '.', *b != '.');
+                        if (r != 0)
+                                return r;
+
+                        a++;
+                        b++;
+                }
+
+                if (isdigit(*a) || isdigit(*b)) {
+                        /* Find the leading numeric segments. One may be an empty string. So,
+                         * numeric segments are always newer than alpha segments. */
+                        for (aa = a; isdigit(*aa); aa++)
+                                ;
+                        for (bb = b; isdigit(*bb); bb++)
+                                ;
+
+                        /* Check if one of the strings was empty, but the other not. */
+                        r = compare3(a != aa, b != bb);
+                        if (r != 0)
+                                return r;
+
+                        /* Skip leading '0', to make 00123 equivalent to 123. */
+                        while (*a == '0')
+                                a++;
+                        while (*b == '0')
+                                b++;
+
+                        /* To compare numeric segments without parsing their values, first compare the
+                         * lengths of the segments. Eg. 12345 vs 123, longer is newer. */
+                        r = compare3(aa - a, bb - b);
+                        if (r != 0)
+                                return r;
+
+                        /* Then, compare them as strings. */
+                        r = compare3(strncmp(a, b, aa - a), 0);
+                        if (r != 0)
+                                return r;
+                } else {
+                        /* Find the leading non-numeric segments. */
+                        for (aa = a; isalpha(*aa); aa++)
+                                ;
+                        for (bb = b; isalpha(*bb); bb++)
+                                ;
+
+                        /* Note that the segments are usually not NUL-terminated. */
+                        r = compare3(strncmp(a, b, min(aa - a, bb - b)), 0);
+                        if (r != 0)
+                                return r;
+
+                        /* Longer is newer, e.g. abc vs abcde. */
+                        r = compare3(aa - a, bb - b);
+                        if (r != 0)
+                                return r;
+                }
+
+                /* The current segments are equivalent. Let's move to the next one. */
+                a = aa;
+                b = bb;
+        }
+}
+EXPORT_SYMBOL(strverscmp);
diff --git a/test/self/Kconfig b/test/self/Kconfig
index 1d6d8ab53a8d..d1ca6a701df3 100644
--- a/test/self/Kconfig
+++ b/test/self/Kconfig
@@ -38,6 +38,8 @@ config SELFTEST_ENABLE_ALL
 	imply SELFTEST_JSON
 	imply SELFTEST_DIGEST
 	imply SELFTEST_MMU
+	imply SELFTEST_REGULATOR
+	imply SELFTEST_STRING
 	help
 	  Selects all self-tests compatible with current configuration
 
@@ -81,4 +83,8 @@ config SELFTEST_DIGEST
 	depends on DIGEST
 	select PRINTF_HEXSTR
 
+config SELFTEST_STRING
+	bool "String library selftest"
+	select VERSION_CMP
+
 endif
diff --git a/test/self/Makefile b/test/self/Makefile
index 269de2e10e88..a66f34671e5a 100644
--- a/test/self/Makefile
+++ b/test/self/Makefile
@@ -11,6 +11,7 @@ obj-$(CONFIG_SELFTEST_FS_RAMFS) += ramfs.o
 obj-$(CONFIG_SELFTEST_JSON) += json.o
 obj-$(CONFIG_SELFTEST_DIGEST) += digest.o
 obj-$(CONFIG_SELFTEST_MMU) += mmu.o
+obj-$(CONFIG_SELFTEST_STRING) += string.o
 
 clean-files := *.dtb *.dtb.S .*.dtc .*.pre .*.dts *.dtb.z
 clean-files += *.dtbo *.dtbo.S .*.dtso
diff --git a/test/self/string.c b/test/self/string.c
new file mode 100644
index 000000000000..f03a7410cd64
--- /dev/null
+++ b/test/self/string.c
@@ -0,0 +1,175 @@
+// SPDX-License-Identifier: GPL-2.0-only
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include <common.h>
+#include <bselftest.h>
+#include <string.h>
+
+BSELFTEST_GLOBALS();
+
+static const char *strverscmp_expect_str(int expect)
+{
+	switch (expect) {
+	case -1: return "<";
+	case  0: return "==";
+	case  1: return ">";
+	default: return "?!";
+	}
+}
+
+static int strverscmp_assert_one(const char *lhs, const char *rhs, int expect)
+{
+	int actual;
+
+	total_tests++;
+
+	actual = strverscmp(lhs, rhs);
+	if (actual != expect) {
+		failed_tests++;
+		printf("(%s %s %s), but (%s %s %s) expected\n",
+		       lhs, strverscmp_expect_str(actual), rhs,
+		       lhs, strverscmp_expect_str(expect), rhs);
+	}
+
+	return actual;
+}
+
+static int __strverscmp_assert(char *expr)
+{
+	const char *token, *tokens[3];
+	int expect = -42;
+	int i = 0;
+
+	while ((token = strsep_unescaped(&expr, " "))) {
+		if (i == 3) {
+			pr_err("invalid expression\n");
+			return -EILSEQ;
+		}
+
+		tokens[i++] = token;
+	}
+
+	if (!strcmp(tokens[1], "<"))
+	    expect = -1;
+	else if (!strcmp(tokens[1], "=="))
+	    expect = 0;
+	else if (!strcmp(tokens[1], ">"))
+	    expect = 1;
+
+	return strverscmp_assert_one(tokens[0], tokens[2], expect);
+}
+
+#define strverscmp_assert(expr) ({ \
+	char __expr_mut[] = expr; \
+	__strverscmp_assert(__expr_mut); \
+})
+
+static void test_strverscmp_spec_examples(void)
+{
+	/*
+	 * Taken from specification at
+	 * https://uapi-group.org/specifications/specs/version_format_specification/#examples
+	 */
+	strverscmp_assert("11 == 11");
+	strverscmp_assert("systemd-123 == systemd-123");
+	strverscmp_assert("bar-123 < foo-123");
+	strverscmp_assert("123a > 123");
+	strverscmp_assert("123.a > 123");
+	strverscmp_assert("123.a < 123.b");
+	strverscmp_assert("123a > 123.a");
+	strverscmp_assert("11α == 11β");
+	strverscmp_assert("A < a");
+	strverscmp_assert_one("", "0", -1);
+	strverscmp_assert("0. > 0");
+	strverscmp_assert("0.0 > 0");
+	strverscmp_assert("0 > ~");
+	strverscmp_assert_one("", "~", 1);
+	strverscmp_assert("1_ == 1");
+	strverscmp_assert("_1 == 1");
+	strverscmp_assert("1_ < 1.2");
+	strverscmp_assert("1_2_3 > 1.3.3");
+	strverscmp_assert("1+ == 1");
+	strverscmp_assert("+1 == 1");
+	strverscmp_assert("1+ < 1.2");
+	strverscmp_assert("1+2+3 > 1.3.3");
+}
+
+static void test_strverscmp_one(const char *newer, const char *older)
+{
+        strverscmp_assert_one(newer, newer,  0);
+        strverscmp_assert_one(newer, older,  1);
+        strverscmp_assert_one(older, newer, -1);
+        strverscmp_assert_one(older, older,  0);
+}
+
+static void test_strverscmp_spec_systemd(void)
+{
+	/*
+	 * Taken from systemd tests at
+	 * 87b7d9b6ff23ec10b66bf53efeabf16ad85d7ad8
+	 */
+        static const char * const versions[] = {
+                "~1", "", "ab", "abb", "abc", "0001", "002", "12", "122", "122.9",
+                "123~rc1", "123", "123-a", "123-a.1", "123-a1", "123-a1.1", "123-3",
+                "123-3.1", "123^patch1", "123^1", "123.a-1" "123.1-1", "123a-1", "124",
+                NULL,
+        };
+        const char * const *p, * const *q;
+
+	for (p = versions; *p; p++)
+		for (q = p + 1; *q; q++)
+                        test_strverscmp_one(*q, *p);
+
+        test_strverscmp_one("123.45-67.89", "123.45-67.88");
+        test_strverscmp_one("123.45-67.89a", "123.45-67.89");
+        test_strverscmp_one("123.45-67.89", "123.45-67.ab");
+        test_strverscmp_one("123.45-67.89", "123.45-67.9");
+        test_strverscmp_one("123.45-67.89", "123.45-67");
+        test_strverscmp_one("123.45-67.89", "123.45-66.89");
+        test_strverscmp_one("123.45-67.89", "123.45-9.99");
+        test_strverscmp_one("123.45-67.89", "123.42-99.99");
+        test_strverscmp_one("123.45-67.89", "123-99.99");
+
+        /* '~' : pre-releases */
+        test_strverscmp_one("123.45-67.89", "123~rc1-99.99");
+        test_strverscmp_one("123-45.67.89", "123~rc1-99.99");
+        test_strverscmp_one("123~rc2-67.89", "123~rc1-99.99");
+        test_strverscmp_one("123^aa2-67.89", "123~rc1-99.99");
+        test_strverscmp_one("123aa2-67.89", "123~rc1-99.99");
+
+        /* '-' : separator between version and release. */
+        test_strverscmp_one("123.45-67.89", "123-99.99");
+        test_strverscmp_one("123^aa2-67.89", "123-99.99");
+        test_strverscmp_one("123aa2-67.89", "123-99.99");
+
+        /* '^' : patch releases */
+        test_strverscmp_one("123.45-67.89", "123^45-67.89");
+        test_strverscmp_one("123^aa2-67.89", "123^aa1-99.99");
+        test_strverscmp_one("123aa2-67.89", "123^aa2-67.89");
+
+        /* '.' : point release */
+        test_strverscmp_one("123aa2-67.89", "123.aa2-67.89");
+        test_strverscmp_one("123.ab2-67.89", "123.aa2-67.89");
+
+        /* invalid characters */
+        strverscmp_assert_one("123_aa2-67.89", "123aa+2-67.89", 0);
+}
+
+static void test_strverscmp(void)
+{
+	test_strverscmp_spec_examples();
+	test_strverscmp_spec_systemd();
+
+	/* and now some corner cases */
+	strverscmp_assert_one(NULL, NULL, 0);
+	strverscmp_assert_one(NULL, "", 0);
+	strverscmp_assert_one("", NULL, 0);
+	strverscmp_assert_one("", "", 0);
+}
+
+static void test_string(void)
+{
+	test_strverscmp();
+}
+bselftest(parser, test_string);
-- 
2.38.5




  parent reply	other threads:[~2023-05-31  6:30 UTC|newest]

Thread overview: 5+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-05-31  6:28 [PATCH 0/3] " Ahmad Fatoum
2023-05-31  6:28 ` [PATCH 1/3] include: sync min/max definitions with Linux Ahmad Fatoum
2023-05-31  6:28 ` [PATCH 2/3] include: minmax.h: implement compare3 helper Ahmad Fatoum
2023-05-31  6:28 ` Ahmad Fatoum [this message]
2023-06-01  7:07 ` [PATCH 0/3] string: import strverscmp_improved from systemd Sascha Hauer

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20230531062853.670751-4-ahmad@a3f.at \
    --to=ahmad@a3f.at \
    --cc=barebox@lists.infradead.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox