lib/filevercmp.c

   1 /*
   2    Copyright (C) 1995 Ian Jackson <iwj10@cus.cam.ac.uk>
   3    Copyright (C) 2001 Anthony Towns <aj@azure.humbug.org.au>
   4    Copyright (C) 2008-2011 Free Software Foundation, Inc.
   5
   6    This program is free software: you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation, either version 3 of the License, or
   9    (at your option) any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  18
  19 #include <config.h>
  20 #include "filevercmp.h"
  21
  22 #include <sys/types.h>
  23 #include <stdlib.h>
  24 #include <stdbool.h>
  25 #include <string.h>
  26 #include <c-ctype.h>
  27 #include <limits.h>
  28
  29 /* The attribute __pure__ was added in gcc 2.96.  */
  30 #undef _GL_ATTRIBUTE_PURE
  31 #if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ >= 96)
  32 # define _GL_ATTRIBUTE_PURE __attribute__ ((__pure__))
  33 #else
  34 # define _GL_ATTRIBUTE_PURE /* empty */
  35 #endif
  36
  37 /* Match a file suffix defined by this regular expression:
  38    /(\.[A-Za-z~][A-Za-z0-9~]*)*$/
  39    Scan the string *STR and return a pointer to the matching suffix, or
  40    NULL if not found.  Upon return, *STR points to terminating NUL.  */
  41 static const char *
  42 match_suffix (const char **str)
  43 {
  44   const char *match = NULL;
  45   bool read_alpha = false;
  46   while (**str)
  47     {
  48       if (read_alpha)
  49         {
  50           read_alpha = false;
  51           if (!c_isalpha (**str) && '~' != **str)
  52             match = NULL;
  53         }
  54       else if ('.' == **str)
  55         {
  56           read_alpha = true;
  57           if (!match)
  58             match = *str;
  59         }
  60       else if (!c_isalnum (**str) && '~' != **str)
  61         match = NULL;
  62       (*str)++;
  63     }
  64   return match;
  65 }
  66
  67 /* verrevcmp helper function */
  68 static inline int
  69 order (unsigned char c)
  70 {
  71   if (c_isdigit (c))
  72     return 0;
  73   else if (c_isalpha (c))
  74     return c;
  75   else if (c == '~')
  76     return -1;
  77   else
  78     return (int) c + UCHAR_MAX + 1;
  79 }
  80
  81 /* slightly modified verrevcmp function from dpkg
  82    S1, S2 - compared string
  83    S1_LEN, S2_LEN - length of strings 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    http://www.debian.org/doc/debian-policy/ch-controlfields.html#s-f-Version */
  91 static int _GL_ATTRIBUTE_PURE
  92 verrevcmp (const char *s1, size_t s1_len, const char *s2, size_t s2_len)
  93 {
  94   size_t s1_pos = 0;
  95   size_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 = (s1_pos == s1_len) ? 0 : order (s1[s1_pos]);
 103           int s2_c = (s2_pos == s2_len) ? 0 : order (s2[s2_pos]);
 104           if (s1_c != s2_c)
 105             return s1_c - s2_c;
 106           s1_pos++;
 107           s2_pos++;
 108         }
 109       while (s1[s1_pos] == '0')
 110         s1_pos++;
 111       while (s2[s2_pos] == '0')
 112         s2_pos++;
 113       while (c_isdigit (s1[s1_pos]) && c_isdigit (s2[s2_pos]))
 114         {
 115           if (!first_diff)
 116             first_diff = s1[s1_pos] - s2[s2_pos];
 117           s1_pos++;
 118           s2_pos++;
 119         }
 120       if (c_isdigit (s1[s1_pos]))
 121         return 1;
 122       if (c_isdigit (s2[s2_pos]))
 123         return -1;
 124       if (first_diff)
 125         return first_diff;
 126     }
 127   return 0;
 128 }
 129
 130 /* Compare version strings S1 and S2.
 131    See filevercmp.h for function description.  */
 132 int
 133 filevercmp (const char *s1, const char *s2)
 134 {
 135   const char *s1_pos;
 136   const char *s2_pos;
 137   const char *s1_suffix, *s2_suffix;
 138   size_t s1_len, s2_len;
 139   int result;
 140
 141   /* easy comparison to see if strings are identical */
 142   int simple_cmp = strcmp (s1, s2);
 143   if (simple_cmp == 0)
 144     return 0;
 145
 146   /* special handle for "", "." and ".." */
 147   if (!*s1)
 148     return -1;
 149   if (!*s2)
 150     return 1;
 151   if (0 == strcmp (".", s1))
 152     return -1;
 153   if (0 == strcmp (".", s2))
 154     return 1;
 155   if (0 == strcmp ("..", s1))
 156     return -1;
 157   if (0 == strcmp ("..", s2))
 158     return 1;
 159
 160   /* special handle for other hidden files */
 161   if (*s1 == '.' && *s2 != '.')
 162     return -1;
 163   if (*s1 != '.' && *s2 == '.')
 164     return 1;
 165   if (*s1 == '.' && *s2 == '.')
 166     {
 167       s1++;
 168       s2++;
 169     }
 170
 171   /* "cut" file suffixes */
 172   s1_pos = s1;
 173   s2_pos = s2;
 174   s1_suffix = match_suffix (&s1_pos);
 175   s2_suffix = match_suffix (&s2_pos);
 176   s1_len = (s1_suffix ? s1_suffix : s1_pos) - s1;
 177   s2_len = (s2_suffix ? s2_suffix : s2_pos) - s2;
 178
 179   /* restore file suffixes if strings are identical after "cut" */
 180   if ((s1_suffix || s2_suffix) && (s1_len == s2_len)
 181       && 0 == strncmp (s1, s2, s1_len))
 182     {
 183       s1_len = s1_pos - s1;
 184       s2_len = s2_pos - s2;
 185     }
 186
 187   result = verrevcmp (s1, s1_len, s2, s2_len);
 188   return result == 0 ? simple_cmp : result;
 189 }