versioncmp.c

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