versioncmp.c

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