Re: sort --sort=version

[Bruce Korb]

Simon Josefsson wrote:
> Bruce Korb <address@hidden> writes:
>
> > Here is the usage text from my latest --sort=version patch (attached),
> > now that paperwork is in order.
>
> What is the status of this work?  I have wanted to use sort this way
> several times but became disappointed that there is no support for it
> every time.

My paperwork is in.  The patch works.  I've submitted it.
Beyond that, I don't know.  Below is a patch I have dated July 5.
Hope that helps.  - Bruce

diff --git a/ChangeLog-2008 b/ChangeLog-2008
index aac9feb..da33f93 100644
--- a/ChangeLog-2008
+++ b/ChangeLog-2008
@@ -1,3 +1,10 @@
+2008-07-05  Bruce Korb  <address@hidden>
+
+       * 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  <address@hidden>

        We *do* need two different version files.
diff --git a/src/sort.c b/src/sort.c
index 9f998a6..6ee3e8c 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -175,6 +175,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;
@@ -1794,6 +1815,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. */

@@ -1833,6 +1880,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
@@ -2689,10 +2740,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';
@@ -2706,6 +2758,8 @@ check_ordering_compatibility (void)
          *p++ = 'M';
        if (key->numeric)
          *p++ = 'n';
+       if (key->version)
+         *p++ = 'V';
        if (key->random)
          *p++ = 'R';
        *p = '\0';
@@ -2807,6 +2861,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;
        }
@@ -2934,7 +2991,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;

@@ -3018,6 +3075,7 @@ main (int argc, char **argv)
        case 'n':
        case 'r':
        case 'R':
+       case 'V':
          {
            char str[2];
            str[0] = c;
@@ -3258,11 +3316,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;
@@ -3273,15 +3336,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 f7275f8..b3b6fc8 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -196,6 +196,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 100755
index 0000000..7410015
--- /dev/null
+++ b/tests/misc/sort-version
@@ -0,0 +1,79 @@
+#!/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
+
+if test $? -eq 0
+then
+    rm -f sort-ver-*
+    (exit 0)
+    exit 0
+fi
+
+exec 1>2
+echo "sorted versions are out of order"
+diff -c ${g_file} ${r_file}
+ls -l sort-ver-*
+(exit 1)
+exit 1