coreutils "sort -b -kSTART,END.ENDCHAR" incompatibility with POSIX

[Paul Eggert]

Yesterday's email exchange with Stuart Allsop caused me to discover a
longstanding bug in coreutils "sort".  This bug causes "sort" to be
incompatible with both POSIX and traditional Unix sort.  Here's a
proposed patch.

2004-04-25  Paul Eggert  <address@hidden>

        Fix POSIX-conformance bug: "sort -k 3,3.5b" is supposed to skip
        leading blanks when computing the location of the field end;
        it is not supposed to skip trailing blanks.  Solaris 8 "sort"
        does conform to POSIX.  Also fix the documentation to clarify
        this and related issues.

        * doc/coreutils.texi (sort invocation): Mention -k earlier, so
        that the options are in alphabetical order.  Describe how -b works
        more-accurately; this involves fixing some examples, too.  Mention
        what happens if the start field falls after an end field or after
        a line end.  Warn about using -k without -b, -g, -M, -n, or -t.
        Add an example of how to sort IPv4 addresses and Apache Common
        Log Format dates.  Remove a duplicate example.
        (Putting the tools together): Use separate options rather
        than agglomerating them.
        * src/sort.c (limfield): Use skipeblanks, not skipsblanks, to
        decode whether to skip leading blanks.
        (trailing_blanks): Remove.
        (fillbuf, getmonth, keycompare): Don't trim trailing blanks.

        * tests/pr/Test.pm: Fix typo in env_default comment.
        * tests/sort/Test.pm: Likewise.
        (18c, 18d): Reverse the order of output lines, so that the
        test cases conform to POSIX.

Index: doc/coreutils.texi
===================================================================
RCS file: /home/meyering/coreutils/cu/doc/coreutils.texi,v
retrieving revision 1.178
diff -p -u -r1.178 coreutils.texi
--- doc/coreutils.texi  12 Apr 2004 09:22:02 -0000      1.178
+++ doc/coreutils.texi  25 Apr 2004 06:39:28 -0000
@@ -3248,6 +3248,17 @@ Other options are:
 
 @table @samp
 
address@hidden -k @var{pos1}[,@var{pos2}]
address@hidden address@hidden,@var{pos2}]
address@hidden -k
address@hidden --key
address@hidden sort field
+Specify a sort field that consists of the part of the line between
address@hidden and @var{pos2} (or the end of the line, if @var{pos2} is
+omitted), @emph{inclusive}.  Fields and character positions are numbered
+starting with 1.  So to sort on the second field, you'd use
address@hidden,2} (@option{-k 2,2}).  See below for more examples.
+
 @item -o @var{output-file}
 @itemx address@hidden
 @opindex -o
@@ -3313,8 +3324,10 @@ string between a non-blank character and
 That is, given the input line @address@hidden foo bar}}, @command{sort} breaks 
it
 into fields @address@hidden foo}} and @address@hidden bar}}.  The field 
separator is
 not considered to be part of either the field preceding or the field
-following.  But note that sort fields that extend to the end of the line,
-as @option{-k 2}, or sort fields consisting of a range, as @option{-k 2,3},
+following, so with @samp{sort @w{-t " "}} the same input line has
+three fields: an empty field, @samp{foo}, and @samp{bar}.
+However, fields that extend to the end of the line,
+as @option{-k 2}, or fields consisting of a range, as @option{-k 2,3},
 retain the field separators present between the endpoints of the range.
 
 To specify a zero byte (@acronym{ASCII} @sc{nul} (Null) character) as
@@ -3344,17 +3357,6 @@ Normally, output only the first of a seq
 equal.  For the @option{--check} (@option{-c}) option,
 check that no pair of consecutive lines compares equal.
 
address@hidden -k @var{pos1}[,@var{pos2}]
address@hidden address@hidden,@var{pos2}]
address@hidden -k
address@hidden --key
address@hidden sort field
-Specify a sort field that consists of the part of the line between
address@hidden and @var{pos2} (or the end of the line, if @var{pos2} is
-omitted), @emph{inclusive}.  Fields and character positions are numbered
-starting with 1.  So to sort on the second field, you'd use
address@hidden,2} (@option{-k 2,2}).  See below for more examples.
-
 @item -z
 @itemx --zero-terminated
 @opindex -z
@@ -3385,7 +3387,8 @@ of the field to use and @var{c} is the n
 from the beginning of the field.  In a start position, an omitted
 @address@hidden stands for the field's first character.  In an end
 position, an omitted or zero @address@hidden stands for the field's
-last character.  If the
+last character.  If the start field falls after the end of the line
+or after the end field, the field is empty.  If the
 @option{-b} option was specified, the @address@hidden part of a field
 specification is counted from the first nonblank character of the field.
 
@@ -3395,7 +3398,12 @@ for that particular field.  The @option{
 attached to either or both of the start and
 end positions of a field specification, and if it is inherited
 from the global options it will be attached to both.
-Keys may span multiple fields.
+If input lines can contain leading or adjacent blanks and @option{-t}
+is not used, then @option{-k} is typically combined with @option{-b},
address@hidden, @option{-M}, or @option{-n}; otherwise the varying
+numbers of leading blanks in fields can cause confusing results.
+
+Keys can span multiple fields.
 
 On older systems, @command{sort} supports an obsolete origin-zero
 syntax @address@hidden address@hidden for specifying sort keys.
@@ -3410,16 +3418,18 @@ Here are some examples to illustrate var
 Sort in descending (reverse) numeric order.
 
 @example
-sort -nr
+sort -n -r
 @end example
 
 @item
-Sort alphabetically, omitting the first and second fields.
+Sort alphabetically, omitting the first and second fields
+and the blanks at the start of the third field.
 This uses a single key composed of the characters beginning
-at the start of field three and extending to the end of each line.
+at the start of the first nonblank character in field three
+and extending to the end of each line.
 
 @example
-sort -k 3
+sort -k 3b
 @end example
 
 @item
@@ -3431,7 +3441,7 @@ Use @samp{:} as the field delimiter.
 sort -t : -k 2,2n -k 5.3,5.4
 @end example
 
-Note that if you had written @option{-k 2} instead of @option{-k 2,2}
+Note that if you had written @option{-k 2n} instead of @option{-k 2,2n}
 @command{sort} would have used all characters beginning in the second field
 and extending to the end of the line as the primary @emph{numeric}
 key.  For the large majority of applications, treating keys spanning
@@ -3447,18 +3457,58 @@ field-end part of the key specifier.
 @item
 Sort the password file on the fifth field and ignore any
 leading blanks.  Sort lines with equal values in field five
-on the numeric user ID in field three.
+on the numeric user ID in field three.  Fields are separated
+by @samp{:}.
 
 @example
 sort -t : -k 5b,5 -k 3,3n /etc/passwd
address@hidden example
-
-An alternative is to use the global numeric modifier @option{-n}.
-
address@hidden
 sort -t : -n -k 5b,5 -k 3,3 /etc/passwd
+sort -t : -b -k 5,5 -k 3,3n /etc/passwd
 @end example
 
+These three commands have equivalent effect.  The first specifies that
+the first key's start position ignores leading blanks and the second
+key is sorted numerically.  The other two commands rely on global
+options being inherited by sort keys that lack modifiers.  The inheritance
+works in this case because @option{-k 5b,5b} and @option{-k 5b,5} are
+equivalent, as the location of a field-end lacking a @address@hidden
+character position is not affected by whether initial blanks are
+skipped.
+
address@hidden
+Sort a set of log files, primarily by IPv4 address and secondarily by
+time stamp.  If two lines' primary and secondary keys are identical,
+output the lines in the same order that they were input.  The log
+files contain lines that look like this:
+
address@hidden
+4.150.156.3 - - [01/Apr/2004:06:31:51 +0000] message 1
+211.24.3.231 - - [24/Apr/2004:20:17:39 +0000] message 2
address@hidden example
+
+Fields are separated by exactly one space.  Sort IPv4 addresses
+lexicographically, e.g., 212.61.52.2 sorts before 212.129.233.201
+because 61 is less than 129.
+
address@hidden
+sort -s -t ' ' -k 4.9n -k 4.5M -k 4.2n -k 4.14,4.21 file*.log |
+sort -s -t '.' -k 1,1n -k 2,2n -k 3,3n -k 4,4n
address@hidden example
+
+This example cannot be done with a single @command{sort} invocation,
+since IPv4 address components are separated by @samp{.} while dates
+come just after a space.  So it is broken down into two invocations of
address@hidden: the first sorts by time stamp and the second by IPv4
+address.  The time stamp is sorted by year, then month, then day, and
+finally by hour-minute-second field, using @option{-k} to isolate each
+field.  Except for hour-minute-second there's no need to specify the
+end of each key field, since the @samp{n} and @samp{M} modifiers sort
+based on leading prefixes that cannot cross field boundaries.  The
+IPv4 addresses are sorted lexicographically.  The second sort uses
address@hidden so that ties in the primary key are broken by the secondary
+key; the first sort uses @samp{-s} so that the combination of the two
+sorts is stable.
+
 @item
 Generate a tags file in case-insensitive sorted order.
 
@@ -3470,21 +3520,6 @@ The use of @option{-print0}, @option{-z}
 that pathnames that contain Line Feed characters will not get broken up
 by the sort operation.
 
-Finally, to ignore both leading and trailing blanks, you
-could have applied the @samp{b} modifier to the field-end specifier
-for the first key,
-
address@hidden
-sort -t : -n -k 5b,5b -k 3,3 /etc/passwd
address@hidden example
-
-or by using the global @option{-b} modifier instead of @option{-n}
-and an explicit @samp{n} with the second key specifier.
-
address@hidden
-sort -t : -b -k 5,5 -k 3,3n /etc/passwd
address@hidden example
-
 @c This example is a bit contrived and needs more explanation.
 @c @item
 @c Sort records separated by an arbitrary string by using a pipe to convert
@@ -12972,7 +13007,7 @@ The final pipeline looks like this:
 
 @smallexample
 $ tr '[A-Z]' '[a-z]' < whats.gnu | tr -cd '[A-Za-z0-9_ \012]' |
-> tr -s '[ ]' '\012' | sort | uniq -c | sort -nr
+> tr -s '[ ]' '\012' | sort | uniq -c | sort -n -r
 @print{}  156 the
 @print{}   60 a
 @print{}   58 to
Index: src/sort.c
===================================================================
RCS file: /home/meyering/coreutils/cu/src/sort.c,v
retrieving revision 1.282
diff -p -u -r1.282 sort.c
--- src/sort.c  20 Apr 2004 15:08:57 -0000      1.282
+++ src/sort.c  25 Apr 2004 04:48:00 -0000
@@ -148,8 +148,8 @@ struct keyfield
   size_t echar;                        /* Additional characters in field. */
   bool const *ignore;          /* Boolean array of characters to ignore. */
   char const *translate;       /* Translation applied to characters. */
-  bool skipsblanks;            /* Skip leading blanks at start. */
-  bool skipeblanks;            /* Skip trailing blanks at finish. */
+  bool skipsblanks;            /* Skip leading blanks when finding start.  */
+  bool skipeblanks;            /* Skip leading blanks when finding end.  */
   bool numeric;                        /* Flag for numeric comparison.  Handle
                                   strings of digits with optional decimal
                                   point, but no exponential notation. */
@@ -912,7 +912,7 @@ limfield (const struct line *line, const
 
   /* If we're skipping leading blanks, don't start counting characters
      until after skipping past any leading blanks.  */
-  if (key->skipsblanks)
+  if (key->skipeblanks)
     while (ptr < lim && blanks[UCHAR (*ptr)])
       ++ptr;
 
@@ -926,17 +926,6 @@ limfield (const struct line *line, const
   return ptr;
 }
 
-/* Return the number of trailing blanks in FIELD, with LEN bytes.  */
-
-static size_t
-trailing_blanks (char const *field, size_t len)
-{
-  size_t i;
-  for (i = len; 0 < i && blanks[UCHAR (field[i - 1])]; i--)
-    continue;
-  return len - i;
-}
-
 /* Fill BUF reading from FP, moving buf->left bytes from the end
    of buf->buf to the beginning first.  If EOF is reached and the
    file wasn't terminated by a newline, supply one.  Set up BUF's line
@@ -1023,11 +1012,6 @@ fillbuf (struct buffer *buf, register FI
                          line_start++;
                      line->keybeg = line_start;
                    }
-                 if (key->skipeblanks)
-                   {
-                     size_t keylen = line->keylim - line->keybeg;
-                     line->keylim -= trailing_blanks (line->keybeg, keylen);
-                   }
                }
 
              line_start = ptr;
@@ -1312,7 +1296,6 @@ getmonth (const char *s, size_t len)
   month = alloca (len + 1);
   for (i = 0; i < len; ++i)
     month[i] = fold_toupper[UCHAR (s[i])];
-  len -= trailing_blanks (month, len);
   month[len] = '\0';
 
   do
@@ -1357,12 +1340,6 @@ keycompare (const struct line *a, const 
       /* Find the lengths. */
       size_t lena = lima <= texta ? 0 : lima - texta;
       size_t lenb = limb <= textb ? 0 : limb - textb;
-
-      if (key->skipeblanks)
-       {
-         lena -= trailing_blanks (texta, lena);
-         lenb -= trailing_blanks (textb, lenb);
-       }
 
       /* Actually compare the fields. */
       if (key->numeric | key->general_numeric)
Index: tests/pr/Test.pm
===================================================================
RCS file: /home/meyering/coreutils/cu/tests/pr/Test.pm,v
retrieving revision 1.16
diff -p -u -r1.16 Test.pm
--- tests/pr/Test.pm    9 Aug 2002 22:13:37 -0000       1.16
+++ tests/pr/Test.pm    25 Apr 2004 06:24:50 -0000
@@ -3,7 +3,7 @@ package Test;
 require 5.002;
 use strict;
 
-# Tell head to accept old-style options like `-1'.
+# Tell pr to accept old-style options like operand-less `-S'.
 $Test::env_default = ['_POSIX2_VERSION=199209'];
 
 my @tv = (
Index: tests/sort/Test.pm
===================================================================
RCS file: /home/meyering/coreutils/cu/tests/sort/Test.pm,v
retrieving revision 1.27
diff -p -u -r1.27 Test.pm
--- tests/sort/Test.pm  4 Sep 2003 22:11:16 -0000       1.27
+++ tests/sort/Test.pm  25 Apr 2004 05:00:58 -0000
@@ -3,7 +3,7 @@ package Test;
 require 5.002;
 use strict;
 
-# Tell head to accept old-style options like `-1'.
+# Tell sort to accept old-style options like `-1'.
 $Test::env_default = ['_POSIX2_VERSION=199209'];
 
 my @tv = (
@@ -162,15 +162,16 @@ my @tv = (
 # key specifier when a key-specific option (`n' in this case) is used.
 ["18b", '-b -k1.1,1.2n', " 901\n100\n", " 901\n100\n", 0],
 
-# No change from above because the `b' on the key-end part of the
-# key specifier makes sort ignore only trailing blanks
-["18c", '-k1.1,1.2nb', " 901\n100\n", " 901\n100\n", 0],
-
-# Here we're comparing `90' and `10', because the `b' on the key-start
-# specifier makes sort ignore *leading* blanks on that key.
-["18d", '-k1.1b,1.2n', " 901\n100\n", "100\n 901\n", 0],
+# Here we're comparing ` 90' and `10', because the `b' on the key-end specifier
+# makes sort ignore leading blanks when determining that key's *end*.
+["18c", '-k1.1,1.2nb', " 901\n100\n", "100\n 901\n", 0],
+
+# Here we're comparing `9' and `10', because the `b' on the key-start specifier
+# makes sort ignore leading blanks when determining that key's *start*.
+["18d", '-k1.1b,1.2n', " 901\n100\n", " 901\n100\n", 0],
 
-# Equivalent to above, except it ignores both leading and trailing blanks.
+# This compares `90' and `10', as it ignores leading blanks for both
+# key start and key end.
 ["18e", '-nb -k1.1,1.2', " 901\n100\n", "100\n 901\n", 0],
 
 # This looks odd, but works properly -- 2nd keyspec is never