versioncmp.c

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