versioncmp: use earliest-longest contained suffix to determine sorting order
[git/git.git] / versioncmp.c
CommitLineData
9ef176b5 1#include "cache.h"
d811c8e1 2#include "string-list.h"
9ef176b5
NTND
3
4/*
5 * versioncmp(): copied from string/strverscmp.c in glibc commit
6 * ee9247c38a8def24a59eb5cfb7196a98bef8cfdc, reformatted to Git coding
7 * style. The implementation is under LGPL-2.1 and Git relicenses it
8 * to GPLv2.
9 */
10
11/*
12 * states: S_N: normal, S_I: comparing integral part, S_F: comparing
13 * fractionnal parts, S_Z: idem but with leading Zeroes only
14 */
15#define S_N 0x0
16#define S_I 0x3
17#define S_F 0x6
18#define S_Z 0x9
19
20/* result_type: CMP: return diff; LEN: compare using len_diff/diff */
21#define CMP 2
22#define LEN 3
23
d811c8e1
NTND
24static const struct string_list *prereleases;
25static int initialized;
26
27/*
109064a0 28 * off is the offset of the first different character in the two strings
b8231660 29 * s1 and s2. If either s1 or s2 contains a prerelease suffix containing
51acfa9d
SG
30 * that offset or a suffix ends right before that offset, then that
31 * string will be forced to be on top.
d811c8e1 32 *
b8231660 33 * If both s1 and s2 contain a (different) suffix around that position,
109064a0
SG
34 * their order is determined by the order of those two suffixes in the
35 * configuration.
b8231660
SG
36 * If any of the strings contains more than one different suffixes around
37 * that position, then that string is sorted according to the contained
51acfa9d
SG
38 * suffix which starts at the earliest offset in that string.
39 * If more than one different contained suffixes start at that earliest
40 * offset, then that string is sorted according to the longest of those
41 * suffixes.
d811c8e1
NTND
42 *
43 * Return non-zero if *diff contains the return value for versioncmp()
44 */
109064a0
SG
45static int swap_prereleases(const char *s1,
46 const char *s2,
47 int off,
d811c8e1
NTND
48 int *diff)
49{
d811c8e1 50 int i, i1 = -1, i2 = -1;
51acfa9d 51 int start_at1 = off, start_at2 = off, match_len1 = -1, match_len2 = -1;
d811c8e1
NTND
52
53 for (i = 0; i < prereleases->nr; i++) {
54 const char *suffix = prereleases->items[i].string;
51acfa9d 55 int j, start, end, suffix_len = strlen(suffix);
b8231660 56 if (suffix_len < off)
51acfa9d 57 start = off - suffix_len;
b8231660
SG
58 else
59 start = 0;
51acfa9d
SG
60 end = match_len1 < suffix_len ? start_at1 : start_at1-1;
61 for (j = start; j <= end; j++)
62 if (starts_with(s1 + j, suffix)) {
b8231660 63 i1 = i;
51acfa9d
SG
64 start_at1 = j;
65 match_len1 = suffix_len;
b8231660
SG
66 break;
67 }
51acfa9d
SG
68 end = match_len2 < suffix_len ? start_at2 : start_at2-1;
69 for (j = start; j <= end; j++)
70 if (starts_with(s2 + j, suffix)) {
b8231660 71 i2 = i;
51acfa9d
SG
72 start_at2 = j;
73 match_len2 = suffix_len;
b8231660
SG
74 break;
75 }
d811c8e1
NTND
76 }
77 if (i1 == -1 && i2 == -1)
78 return 0;
51acfa9d
SG
79 if (i1 == i2)
80 /* Found the same suffix in both, e.g. "-rc" in "v1.0-rcX"
81 * and "v1.0-rcY": the caller should decide based on "X"
82 * and "Y". */
83 return 0;
84
d811c8e1
NTND
85 if (i1 >= 0 && i2 >= 0)
86 *diff = i1 - i2;
87 else if (i1 >= 0)
88 *diff = -1;
89 else /* if (i2 >= 0) */
90 *diff = 1;
91 return 1;
92}
9ef176b5
NTND
93
94/*
95 * Compare S1 and S2 as strings holding indices/version numbers,
96 * returning less than, equal to or greater than zero if S1 is less
97 * than, equal to or greater than S2 (for more info, see the texinfo
98 * doc).
99 */
100
101int versioncmp(const char *s1, const char *s2)
102{
103 const unsigned char *p1 = (const unsigned char *) s1;
104 const unsigned char *p2 = (const unsigned char *) s2;
105 unsigned char c1, c2;
106 int state, diff;
107
108 /*
109 * Symbol(s) 0 [1-9] others
110 * Transition (10) 0 (01) d (00) x
111 */
112 static const uint8_t next_state[] = {
113 /* state x d 0 */
114 /* S_N */ S_N, S_I, S_Z,
115 /* S_I */ S_N, S_I, S_I,
116 /* S_F */ S_N, S_F, S_F,
117 /* S_Z */ S_N, S_F, S_Z
118 };
119
120 static const int8_t result_type[] = {
121 /* state x/x x/d x/0 d/x d/d d/0 0/x 0/d 0/0 */
122
123 /* S_N */ CMP, CMP, CMP, CMP, LEN, CMP, CMP, CMP, CMP,
124 /* S_I */ CMP, -1, -1, +1, LEN, LEN, +1, LEN, LEN,
125 /* S_F */ CMP, CMP, CMP, CMP, CMP, CMP, CMP, CMP, CMP,
126 /* S_Z */ CMP, +1, +1, -1, CMP, CMP, -1, CMP, CMP
127 };
128
129 if (p1 == p2)
130 return 0;
131
132 c1 = *p1++;
133 c2 = *p2++;
134 /* Hint: '0' is a digit too. */
135 state = S_N + ((c1 == '0') + (isdigit (c1) != 0));
136
137 while ((diff = c1 - c2) == 0) {
138 if (c1 == '\0')
139 return diff;
140
141 state = next_state[state];
142 c1 = *p1++;
143 c2 = *p2++;
144 state += (c1 == '0') + (isdigit (c1) != 0);
145 }
146
d811c8e1
NTND
147 if (!initialized) {
148 initialized = 1;
149 prereleases = git_config_get_value_multi("versionsort.prereleasesuffix");
150 }
109064a0
SG
151 if (prereleases && swap_prereleases(s1, s2, (const char *) p1 - s1 - 1,
152 &diff))
d811c8e1
NTND
153 return diff;
154
9ef176b5
NTND
155 state = result_type[state * 3 + (((c2 == '0') + (isdigit (c2) != 0)))];
156
157 switch (state) {
158 case CMP:
159 return diff;
160
161 case LEN:
162 while (isdigit (*p1++))
163 if (!isdigit (*p2++))
164 return 1;
165
166 return isdigit (*p2) ? -1 : diff;
167
168 default:
169 return state;
170 }
171}