versioncmp.c

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