lib/filevercmp.c

   1 /* Compare file names containing version numbers.
   2
   3    Copyright (C) 1995 Ian Jackson <iwj10@cus.cam.ac.uk>
   4    Copyright (C) 2001 Anthony Towns <aj@azure.humbug.org.au>
   5    Copyright (C) 2008-2024 Free Software Foundation, Inc.
   6
   7    This file is free software: you can redistribute it and/or modify
   8    it under the terms of the GNU Lesser General Public License as
   9    published by the Free Software Foundation, either version 3 of the
  10    License, or (at your option) any later version.
  11
  12    This file is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU Lesser General Public License for more details.
  16
  17    You should have received a copy of the GNU Lesser General Public License
  18    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  19
  20 #include <config.h>
  21 #include "filevercmp.h"
  22
  23 #include <c-ctype.h>
  24 #include <limits.h>
  25 #include <idx.h>
  26
  27 /* Return the length of a prefix of S that corresponds to the suffix
  28    defined by this extended regular expression in the C locale:
  29      (\.[A-Za-z~][A-Za-z0-9~]*)*$
  30    Use the longest suffix matching this regular expression,
  31    except do not use all of S as a suffix if S is nonempty.
  32    If *LEN is -1, S is a string; set *LEN to S's length.
  33    Otherwise, *LEN should be nonnegative, S is a char array,
  34    and *LEN does not change.  */
  35 static idx_t
  36 file_prefixlen (char const *s, ptrdiff_t *len)
  37 {
  38   size_t n = *len;  /* SIZE_MAX if N == -1.  */
  39   idx_t prefixlen = 0;
  40
  41   for (idx_t i = 0; ; )
  42     {
  43       if (*len < 0 ? !s[i] : i == n)
  44         {
  45           *len = i;
  46           return prefixlen;
  47         }
  48
  49       i++;
  50       prefixlen = i;
  51       while (i + 1 < n && s[i] == '.' && (c_isalpha (s[i + 1])
  52                                           || s[i + 1] == '~'))
  53         for (i += 2; i < n && (c_isalnum (s[i]) || s[i] == '~'); i++)
  54           continue;
  55     }
  56 }
  57
  58 /* Return a version sort comparison value for S's byte at position POS.
  59    S has length LEN.  If POS == LEN, sort before all non-'~' bytes.  */
  60
  61 static int
  62 order (char const *s, idx_t pos, idx_t len)
  63 {
  64   if (pos == len)
  65     return -1;
  66
  67   unsigned char c = s[pos];
  68   if (c_isdigit (c))
  69     return 0;
  70   else if (c_isalpha (c))
  71     return c;
  72   else if (c == '~')
  73     return -2;
  74   else
  75     {
  76       static_assert (UCHAR_MAX <= (INT_MAX - 1 - 2) / 2);
  77       return c + UCHAR_MAX + 1;
  78     }
  79 }
  80
  81 /* slightly modified verrevcmp function from dpkg
  82    S1, S2 - compared char array
  83    S1_LEN, S2_LEN - length of arrays to be scanned
  84
  85    This implements the algorithm for comparison of version strings
  86    specified by Debian and now widely adopted.  The detailed
  87    specification can be found in the Debian Policy Manual in the
  88    section on the 'Version' control field.  This version of the code
  89    implements that from s5.6.12 of Debian Policy v3.8.0.1
  90    https://www.debian.org/doc/debian-policy/ch-controlfields.html#s-f-Version */
  91 static int _GL_ATTRIBUTE_PURE
  92 verrevcmp (const char *s1, idx_t s1_len, const char *s2, idx_t s2_len)
  93 {
  94   idx_t s1_pos = 0;
  95   idx_t s2_pos = 0;
  96   while (s1_pos < s1_len || s2_pos < s2_len)
  97     {
  98       int first_diff = 0;
  99       while ((s1_pos < s1_len && !c_isdigit (s1[s1_pos]))
 100              || (s2_pos < s2_len && !c_isdigit (s2[s2_pos])))
 101         {
 102           int s1_c = order (s1, s1_pos, s1_len);
 103           int s2_c = order (s2, s2_pos, s2_len);
 104           if (s1_c != s2_c)
 105             return s1_c - s2_c;
 106           s1_pos++;
 107           s2_pos++;
 108         }
 109       while (s1_pos < s1_len && s1[s1_pos] == '0')
 110         s1_pos++;
 111       while (s2_pos < s2_len && s2[s2_pos] == '0')
 112         s2_pos++;
 113       while (s1_pos < s1_len && s2_pos < s2_len
 114              && c_isdigit (s1[s1_pos]) && c_isdigit (s2[s2_pos]))
 115         {
 116           if (!first_diff)
 117             first_diff = s1[s1_pos] - s2[s2_pos];
 118           s1_pos++;
 119           s2_pos++;
 120         }
 121       if (s1_pos < s1_len && c_isdigit (s1[s1_pos]))
 122         return 1;
 123       if (s2_pos < s2_len && c_isdigit (s2[s2_pos]))
 124         return -1;
 125       if (first_diff)
 126         return first_diff;
 127     }
 128   return 0;
 129 }
 130
 131 /* Compare version strings S1 and S2.
 132    See filevercmp.h for function description.  */
 133 int
 134 filevercmp (const char *s1, const char *s2)
 135 {
 136   return filenvercmp (s1, -1, s2, -1);
 137 }
 138
 139 /* Compare versions A (of length ALEN) and B (of length BLEN).
 140    See filevercmp.h for function description.  */
 141 int
 142 filenvercmp (char const *a, ptrdiff_t alen, char const *b, ptrdiff_t blen)
 143 {
 144   /* Special case for empty versions.  */
 145   bool aempty = alen < 0 ? !a[0] : !alen;
 146   bool bempty = blen < 0 ? !b[0] : !blen;
 147   if (aempty)
 148     return -!bempty;
 149   if (bempty)
 150     return 1;
 151
 152   /* Special cases for leading ".": "." sorts first, then "..", then
 153      other names with leading ".", then other names.  */
 154   if (a[0] == '.')
 155     {
 156       if (b[0] != '.')
 157         return -1;
 158
 159       bool adot = alen < 0 ? !a[1] : alen == 1;
 160       bool bdot = blen < 0 ? !b[1] : blen == 1;
 161       if (adot)
 162         return -!bdot;
 163       if (bdot)
 164         return 1;
 165
 166       bool adotdot = a[1] == '.' && (alen < 0 ? !a[2] : alen == 2);
 167       bool bdotdot = b[1] == '.' && (blen < 0 ? !b[2] : blen == 2);
 168       if (adotdot)
 169         return -!bdotdot;
 170       if (bdotdot)
 171         return 1;
 172     }
 173   else if (b[0] == '.')
 174     return 1;
 175
 176   /* Cut file suffixes.  */
 177   idx_t aprefixlen = file_prefixlen (a, &alen);
 178   idx_t bprefixlen = file_prefixlen (b, &blen);
 179
 180   /* If both suffixes are empty, a second pass would return the same thing.  */
 181   bool one_pass_only = aprefixlen == alen && bprefixlen == blen;
 182
 183   int result = verrevcmp (a, aprefixlen, b, bprefixlen);
 184
 185   /* Return the initial result if nonzero, or if no second pass is needed.
 186      Otherwise, restore the suffixes and try again.  */
 187   return result || one_pass_only ? result : verrevcmp (a, alen, b, blen);
 188 }