1 /* Compare file names containing version numbers.
2
3 Copyright (C) 1995 Ian Jackson <iwj10@cus.cam.ac.uk>
4 Copyright (C) 2001 Anthony Towns <aj@azure.humbug.org.au>
5 Copyright (C) 2008-2023 Free Software Foundation, Inc.
6
7 This file is free software: you can redistribute it and/or modify
8 it under the terms of the GNU Lesser General Public License as
9 published by the Free Software Foundation, either version 3 of the
10 License, or (at your option) any later version.
11
12 This file is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU Lesser General Public License for more details.
16
17 You should have received a copy of the GNU Lesser General Public License
18 along with this program. If not, see <https://www.gnu.org/licenses/>. */
19
20 #include <config.h>
21 #include "filevercmp.h"
22
23 #include <c-ctype.h>
24 #include <limits.h>
25 #include <idx.h>
26
27 /* Return the length of a prefix of S that corresponds to the suffix
28 defined by this extended regular expression in the C locale:
29 (\.[A-Za-z~][A-Za-z0-9~]*)*$
30 Use the longest suffix matching this regular expression,
31 except do not use all of S as a suffix if S is nonempty.
32 If *LEN is -1, S is a string; set *LEN to S's length.
33 Otherwise, *LEN should be nonnegative, S is a char array,
34 and *LEN does not change. */
35 static idx_t
36 file_prefixlen (char const *s, ptrdiff_t *len)
37 {
38 size_t n = *len; /* SIZE_MAX if N == -1. */
39 idx_t prefixlen = 0;
40
41 for (idx_t i = 0; ; )
42 {
43 if (*len < 0 ? !s[i] : i == n)
44 {
45 *len = i;
46 return prefixlen;
47 }
48
49 i++;
50 prefixlen = i;
51 while (i + 1 < n && s[i] == '.' && (c_isalpha (s[i + 1])
52 || s[i + 1] == '~'))
53 for (i += 2; i < n && (c_isalnum (s[i]) || s[i] == '~'); i++)
54 continue;
55 }
56 }
57
58 /* Return a version sort comparison value for S's byte at position POS.
59 S has length LEN. If POS == LEN, sort before all non-'~' bytes. */
60
61 static int
62 order (char const *s, idx_t pos, idx_t len)
63 {
64 if (pos == len)
65 return -1;
66
67 unsigned char c = s[pos];
68 if (c_isdigit (c))
69 return 0;
70 else if (c_isalpha (c))
71 return c;
72 else if (c == '~')
73 return -2;
74 else
75 {
76 static_assert (UCHAR_MAX <= (INT_MAX - 1 - 2) / 2);
77 return c + UCHAR_MAX + 1;
78 }
79 }
80
81 /* slightly modified verrevcmp function from dpkg
82 S1, S2 - compared char array
83 S1_LEN, S2_LEN - length of arrays to be scanned
84
85 This implements the algorithm for comparison of version strings
86 specified by Debian and now widely adopted. The detailed
87 specification can be found in the Debian Policy Manual in the
88 section on the 'Version' control field. This version of the code
89 implements that from s5.6.12 of Debian Policy v3.8.0.1
90 https://www.debian.org/doc/debian-policy/ch-controlfields.html#s-f-Version */
91 static int _GL_ATTRIBUTE_PURE
92 verrevcmp (const char *s1, idx_t s1_len, const char *s2, idx_t s2_len)
93 {
94 idx_t s1_pos = 0;
95 idx_t s2_pos = 0;
96 while (s1_pos < s1_len || s2_pos < s2_len)
97 {
98 int first_diff = 0;
99 while ((s1_pos < s1_len && !c_isdigit (s1[s1_pos]))
100 || (s2_pos < s2_len && !c_isdigit (s2[s2_pos])))
101 {
102 int s1_c = order (s1, s1_pos, s1_len);
103 int s2_c = order (s2, s2_pos, s2_len);
104 if (s1_c != s2_c)
105 return s1_c - s2_c;
106 s1_pos++;
107 s2_pos++;
108 }
109 while (s1_pos < s1_len && s1[s1_pos] == '0')
110 s1_pos++;
111 while (s2_pos < s2_len && s2[s2_pos] == '0')
112 s2_pos++;
113 while (s1_pos < s1_len && s2_pos < s2_len
114 && c_isdigit (s1[s1_pos]) && c_isdigit (s2[s2_pos]))
115 {
116 if (!first_diff)
117 first_diff = s1[s1_pos] - s2[s2_pos];
118 s1_pos++;
119 s2_pos++;
120 }
121 if (s1_pos < s1_len && c_isdigit (s1[s1_pos]))
122 return 1;
123 if (s2_pos < s2_len && c_isdigit (s2[s2_pos]))
124 return -1;
125 if (first_diff)
126 return first_diff;
127 }
128 return 0;
129 }
130
131 /* Compare version strings S1 and S2.
132 See filevercmp.h for function description. */
133 int
134 filevercmp (const char *s1, const char *s2)
135 {
136 return filenvercmp (s1, -1, s2, -1);
137 }
138
139 /* Compare versions A (of length ALEN) and B (of length BLEN).
140 See filevercmp.h for function description. */
141 int
142 filenvercmp (char const *a, ptrdiff_t alen, char const *b, ptrdiff_t blen)
143 {
144 /* Special case for empty versions. */
145 bool aempty = alen < 0 ? !a[0] : !alen;
146 bool bempty = blen < 0 ? !b[0] : !blen;
147 if (aempty)
148 return -!bempty;
149 if (bempty)
150 return 1;
151
152 /* Special cases for leading ".": "." sorts first, then "..", then
153 other names with leading ".", then other names. */
154 if (a[0] == '.')
155 {
156 if (b[0] != '.')
157 return -1;
158
159 bool adot = alen < 0 ? !a[1] : alen == 1;
160 bool bdot = blen < 0 ? !b[1] : blen == 1;
161 if (adot)
162 return -!bdot;
163 if (bdot)
164 return 1;
165
166 bool adotdot = a[1] == '.' && (alen < 0 ? !a[2] : alen == 2);
167 bool bdotdot = b[1] == '.' && (blen < 0 ? !b[2] : blen == 2);
168 if (adotdot)
169 return -!bdotdot;
170 if (bdotdot)
171 return 1;
172 }
173 else if (b[0] == '.')
174 return 1;
175
176 /* Cut file suffixes. */
177 idx_t aprefixlen = file_prefixlen (a, &alen);
178 idx_t bprefixlen = file_prefixlen (b, &blen);
179
180 /* If both suffixes are empty, a second pass would return the same thing. */
181 bool one_pass_only = aprefixlen == alen && bprefixlen == blen;
182
183 int result = verrevcmp (a, aprefixlen, b, bprefixlen);
184
185 /* Return the initial result if nonzero, or if no second pass is needed.
186 Otherwise, restore the suffixes and try again. */
187 return result || one_pass_only ? result : verrevcmp (a, alen, b, blen);
188 }