sort: new option, --sort=version, for version number ordering

* src/sort.c [struct keyfield] (version): New member.
(usage): Describe --version-sort.
(sort_options): Add 'V'.
(long_options): Add "version-sort".
(CHECK_TABLE, _ct_, SORT_TABLE, _st_): Define new macros.
(check_args, sort_args, sort_types): Use these new macros in declarations.
(ARGMATCH_VERIFY): Remove use.  No longer needed.
(compare_version): New function.
(key_compare): Add a case.
(check_ordering_compatibility): Handle new type.
(main): Likewise.  Reformat two expressions for readability.
* tests/misc/sort-version: new test file
* tests/Makefile.am: add it to the list
* doc/coreutils.texi (sort invocation): Document it.
* NEWS: Mention the new feature.

6 files changed, 175 insertions, 20 deletions

diff --git a/ChangeLog-2008 b/ChangeLog-2008
index aac9febeb..da33f93f8 100644
--- a/ChangeLog-2008
+++ b/ChangeLog-2008
@@ -1,3 +1,10 @@
+2008-07-05  Bruce Korb  <bkorb@gnu.org>
+
+	* src/sort.c: implement version number sort
+	(compare_version): new procedure to do it.
+	* tests/misc/sort-version: new test file
+	* tests/Makefile.am: add it to the list
+
 2008-02-07  Jim Meyering  <meyering@redhat.com>
 
 	We *do* need two different version files.
diff --git a/NEWS b/NEWS
index 0c8cb8fb4..72c885ccf 100644
--- a/NEWS
+++ b/NEWS
@@ -39,6 +39,9 @@ GNU coreutils NEWS                                    -*- outline -*-
   represents the maximum number of inputs that will be merged at once.
   When processing more than NMERGE inputs, sort uses temporary files.
 
+  sort accepts still another new option --version-sort, specifying that
+  ordering is to be based on strverscmp(3).
+
 ** Bug fixes
 
   chcon --verbose now prints a newline after each message
diff --git a/doc/coreutils.texi b/doc/coreutils.texi
index cfd283d80..229154281 100644
--- a/doc/coreutils.texi
+++ b/doc/coreutils.texi
@@ -3733,6 +3733,16 @@ Neither a leading @samp{+} nor exponential notation is recognized.
 To compare such strings numerically, use the
 @option{--general-numeric-sort} (@option{-g}) option.
 
+@item -V
+@itemx --version-sort
+@opindex -V
+@opindex --version-sort
+@cindex version number sort
+@vindex LC_NUMERIC
+Sort per @code{strverscmp(3)}.  This is a normal string comparison, except
+that embedded decimal numbers are sorted by numeric value
+(see @option{--numeric-sort} above).
+
 @item -r
 @itemx --reverse
 @opindex -r
diff --git a/src/sort.c b/src/sort.c
index 92f400a96..4e5fc84c7 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -178,6 +178,7 @@ struct keyfield
 				   Handle numbers in exponential notation. */
   bool month;			/* Flag for comparison by month name. */
   bool reverse;			/* Reverse the sense of comparison. */
+  bool version;			/* sort by version number */
   struct keyfield *next;	/* Next keyfield to try. */
 };
 
@@ -336,10 +337,11 @@ Ordering options:\n\
   -M, --month-sort            compare (unknown) < `JAN' < ... < `DEC'\n\
   -n, --numeric-sort          compare according to string numerical value\n\
   -R, --random-sort           sort by random hash of keys\n\
+  -V, --version-sort          sort by numeric version (see strverscmp(3C))\n\
       --random-source=FILE    get random bytes from FILE (default /dev/urandom)\n\
       --sort=WORD             sort according to WORD:\n\
                                 general-numeric -g, month -M, numeric -n,\n\
-                                random -R\n\
+                                random -R, version -V\n\
   -r, --reverse               reverse the result of comparisons\n\
 \n\
 "), stdout);
@@ -418,7 +420,7 @@ enum
   SORT_OPTION
 };
 
-static char const short_options[] = "-bcCdfgik:mMno:rRsS:t:T:uy:z";
+static char const short_options[] = "-bcCdfgik:mMno:rRsS:t:T:uVy:z";
 
 static struct option const long_options[] =
 {
@@ -434,6 +436,7 @@ static struct option const long_options[] =
   {"merge", no_argument, NULL, 'm'},
   {"month-sort", no_argument, NULL, 'M'},
   {"numeric-sort", no_argument, NULL, 'n'},
+  {"version-sort", no_argument, NULL, 'V'},
   {"random-sort", no_argument, NULL, 'R'},
   {"random-source", required_argument, NULL, RANDOM_SOURCE_OPTION},
   {"sort", required_argument, NULL, SORT_OPTION},
@@ -451,25 +454,43 @@ static struct option const long_options[] =
   {NULL, 0, NULL, 0},
 };
 
+#define CHECK_TABLE \
+  _ct_("quiet",          'C') \
+  _ct_("silent",         'C') \
+  _ct_("diagnose-first", 'c')
+
 static char const *const check_args[] =
 {
-  "quiet", "silent", "diagnose-first", NULL
+#define _ct_(_s, _c) _s,
+  CHECK_TABLE NULL
+#undef  _ct_
 };
 static char const check_types[] =
 {
-  'C', 'C', 'c'
+#define _ct_(_s, _c) _c,
+  CHECK_TABLE
+#undef  _ct_
 };
-ARGMATCH_VERIFY (check_args, check_types);
+
+#define SORT_TABLE \
+  _st_("general-numeric", 'g') \
+  _st_("month",           'M') \
+  _st_("numeric",         'n') \
+  _st_("random",          'R') \
+  _st_("version",         'V')
 
 static char const *const sort_args[] =
 {
-  "general-numeric", "month", "numeric", "random", NULL
+#define _st_(_s, _c) _s,
+  SORT_TABLE NULL
+#undef  _st_
 };
 static char const sort_types[] =
 {
-  'g', 'M', 'n', 'R'
+#define _st_(_s, _c) _c,
+  SORT_TABLE
+#undef  _st_
 };
-ARGMATCH_VERIFY (sort_args, sort_types);
 
 /* The set of signals that are caught.  */
 static sigset_t caught_signals;
@@ -1796,6 +1817,32 @@ compare_random (char *restrict texta, size_t lena,
   return diff;
 }
 
+/* Compare the keys TEXTA (of length LENA) and TEXTB (of length LENB)
+   using strverscmp.  */
+
+static int
+compare_version (char *restrict texta, size_t lena,
+                char *restrict textb, size_t lenb)
+{
+  int diff;
+
+  /*
+   *  It is necessary to save the character after the end of the field.
+   *  "strverscmp" works with NUL terminated strings.  Our blocks of
+   *  text are not necessarily terminated with a NUL byte.
+   */
+  char sv_a = texta[lena];
+  char sv_b = textb[lenb];
+
+  texta[lena] = textb[lenb] = '\0';
+  diff = strverscmp (texta, textb);
+
+  texta[lena] = sv_a;
+  textb[lenb] = sv_b;
+
+  return diff;
+}
+
 /* Compare two lines A and B trying every key in sequence until there
    are no more keys or a difference is found. */
 
@@ -1835,6 +1882,10 @@ keycompare (const struct line *a, const struct line *b)
 		  (texta, textb));
 	  *lima = savea, *limb = saveb;
 	}
+
+      else if (key->version)
+        diff = compare_version (texta, lena, textb, lenb);
+
       else if (key->month)
 	diff = getmonth (texta, lena) - getmonth (textb, lenb);
       /* Sorting like this may become slow, so in a simple locale the user
@@ -2691,10 +2742,11 @@ check_ordering_compatibility (void)
 
   for (key = keylist; key; key = key->next)
     if ((1 < (key->random + key->numeric + key->general_numeric + key->month
-	      + !!key->ignore))
+	      + key->version + !!key->ignore))
 	|| (key->random && key->translate))
       {
-	char opts[7];
+        /* The following is too big, but guaranteed to be "big enough". */
+	char opts[sizeof short_options];
 	char *p = opts;
 	if (key->ignore == nondictionary)
 	  *p++ = 'd';
@@ -2708,6 +2760,8 @@ check_ordering_compatibility (void)
 	  *p++ = 'M';
 	if (key->numeric)
 	  *p++ = 'n';
+	if (key->version)
+	  *p++ = 'V';
 	if (key->random)
 	  *p++ = 'R';
 	*p = '\0';
@@ -2809,6 +2863,9 @@ set_ordering (const char *s, struct keyfield *key, enum blanktype blanktype)
 	case 'r':
 	  key->reverse = true;
 	  break;
+	case 'V':
+	  key->version = true;
+	  break;
 	default:
 	  return (char *) s;
 	}
@@ -2936,7 +2993,7 @@ main (int argc, char **argv)
   gkey.sword = gkey.eword = SIZE_MAX;
   gkey.ignore = NULL;
   gkey.translate = NULL;
-  gkey.numeric = gkey.general_numeric = gkey.random = false;
+  gkey.numeric = gkey.general_numeric = gkey.random = gkey.version = false;
   gkey.month = gkey.reverse = false;
   gkey.skipsblanks = gkey.skipeblanks = false;
 
@@ -3020,6 +3077,7 @@ main (int argc, char **argv)
 	case 'n':
 	case 'r':
 	case 'R':
+	case 'V':
 	  {
 	    char str[2];
 	    str[0] = c;
@@ -3260,11 +3318,16 @@ main (int argc, char **argv)
   /* Inheritance of global options to individual keys. */
   for (key = keylist; key; key = key->next)
     {
-      if (! (key->ignore || key->translate
-             || (key->skipsblanks | key->reverse
-                 | key->skipeblanks | key->month | key->numeric
-                 | key->general_numeric
-                 | key->random)))
+      if (! (key->ignore
+	     || key->translate
+	     || (key->skipsblanks
+		 | key->reverse
+		 | key->skipeblanks
+		 | key->month
+		 | key->numeric
+		 | key->version
+		 | key->general_numeric
+		 | key->random)))
         {
           key->ignore = gkey.ignore;
           key->translate = gkey.translate;
@@ -3275,15 +3338,21 @@ main (int argc, char **argv)
           key->general_numeric = gkey.general_numeric;
           key->random = gkey.random;
           key->reverse = gkey.reverse;
+          key->version = gkey.version;
         }
 
       need_random |= key->random;
     }
 
-  if (!keylist && (gkey.ignore || gkey.translate
-		   || (gkey.skipsblanks | gkey.skipeblanks | gkey.month
-		       | gkey.numeric | gkey.general_numeric
-                       | gkey.random)))
+  if (!keylist && (gkey.ignore
+		   || gkey.translate
+		   || (gkey.skipsblanks
+		       | gkey.skipeblanks
+		       | gkey.month
+		       | gkey.numeric
+		       | gkey.general_numeric
+		       | gkey.random
+		       | gkey.version)))
     {
       insertkey (&gkey);
       need_random |= gkey.random;
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 7bdf88aad..5a57ca993 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -198,6 +198,7 @@ TESTS =						\
   misc/sort-files0-from				\
   misc/sort-merge				\
   misc/sort-rand				\
+  misc/sort-version				\
   misc/split-a					\
   misc/split-fail				\
   misc/split-l					\
diff --git a/tests/misc/sort-version b/tests/misc/sort-version
new file mode 100644
index 000000000..a4ebd400f
--- /dev/null
+++ b/tests/misc/sort-version
@@ -0,0 +1,65 @@
+#!/usr/bin/echo do-not-run-this-directly.-Use-a-shell
+# -*- Mode: shell-script -*-
+
+if test "$VERBOSE" = yes; then
+  set -x
+  sort --version
+fi
+
+. $top_srcdir/tests/test-lib.sh
+
+s_file=sort-ver-src
+g_file=sort-ver-good
+r_file=sort-ver-res
+
+cat > $s_file <<- _EOF_
+	string start 5.0.0 end of str
+	string start 5.00.0 end of str
+	string start 5.1.0 end of str
+	string start 5.10.0 end of str
+	string start 5.2.0 end of str
+	string start 5.20.0 end of str
+	string start 5.3.0 end of str
+	string start 5.30.0 end of str
+	string start 5.4.0 end of str
+	string start 5.40.0 end of str
+	string start 5.5.0 end of str
+	string start 5.50.0 end of str
+	string start 5.6.0 end of str
+	string start 5.60.0 end of str
+	string start 5.7.0 end of str
+	string start 5.70.0 end of str
+	string start 5.8.0 end of str
+	string start 5.80.0 end of str
+	string start 5.9.0 end of str
+	string start 5.90.0 end of str
+	_EOF_
+
+
+cat > $g_file <<- _EOF_
+	string start 5.00.0 end of str
+	string start 5.0.0 end of str
+	string start 5.1.0 end of str
+	string start 5.2.0 end of str
+	string start 5.3.0 end of str
+	string start 5.4.0 end of str
+	string start 5.5.0 end of str
+	string start 5.6.0 end of str
+	string start 5.7.0 end of str
+	string start 5.8.0 end of str
+	string start 5.9.0 end of str
+	string start 5.10.0 end of str
+	string start 5.20.0 end of str
+	string start 5.30.0 end of str
+	string start 5.40.0 end of str
+	string start 5.50.0 end of str
+	string start 5.60.0 end of str
+	string start 5.70.0 end of str
+	string start 5.80.0 end of str
+	string start 5.90.0 end of str
+	_EOF_
+
+fail=0
+sort --sort=version -o $r_file $s_file
+compare $g_file $r_file >/dev/null 2>&1 || fail=1
+(exit $fail) ; exit $fail