Keep expected behaviour for [a-z] and [A-z] (Bug 23393).

In commit 9479b6d5e08eacce06c6ab60abc9b2f4eb8b71e4 we updated all of
the collation data to harmonize with the new version of ISO 14651
which is derived from Unicode 9.0.0.  This collation update brought
with it some changes to locales which were not desirable by some
users, in particular it altered the meaning of the
locale-dependent-range regular expression, namely [a-z] and [A-Z], and
for en_US it caused uppercase letters to be matched by [a-z] for the
first time.  The matching of uppercase letters by [a-z] is something
which is already known to users of other locales which have this
property, but this change could cause significant problems to en_US
and other similar locales that had never had this change before.
Whether this behaviour is desirable or not is contentious and GNU Awk
has this to say on the topic:
https://www.gnu.org/software/gawk/manual/html_node/Ranges-and-Locales.html
While the POSIX standard also has this further to say: "RE Bracket
Expression":
http://pubs.opengroup.org/onlinepubs/9699919799/xrat/V4_xbd_chap09.html
"The current standard leaves unspecified the behavior of a range
expression outside the POSIX locale. ... As noted above, efforts were
made to resolve the differences, but no solution has been found that
would be specific enough to allow for portable software while not
invalidating existing implementations."
In glibc we implement the requirement of ISO POSIX-2:1993 and use
collation element order (CEO) to construct the range expression, the
API internally is __collseq_table_lookup().  The fact that we use CEO
and also have 4-level weights on each collation rule means that we can
in practice reorder the collation rules in iso14651_t1_common (the new
data) to provide consistent range expression resolution *and* the
weights should maintain the expected total order.  Therefore this
patch does three things:

* Reorder the collation rules for the LATIN script in
  iso14651_t1_common to deinterlace uppercase and lowercase letters in
  the collation element orders.

* Adds new test data en_US.UTF-8.in for sort-test.sh which exercises
  strcoll* and strxfrm* and ensures the ISO 14651 collation remains.

* Add back tests to tst-fnmatch.input and tst-regexloc.c which
  exercise that [a-z] does not match A or Z.

The reordering of the ISO 14651 data is done in an entirely mechanical
fashion using the following program attached to the bug:
https://sourceware.org/bugzilla/show_bug.cgi?id=23393#c28

It is up for discussion if the iso14651_t1_common data should be
refined further to have 3 very tight collation element ranges that
include only a-z, A-Z, and 0-9, which would implement the solution
sought after in:
https://sourceware.org/bugzilla/show_bug.cgi?id=23393#c12
and implemented here:
https://www.sourceware.org/ml/libc-alpha/2018-07/msg00854.html

No regressions on x86_64.
Verified that removal of the iso14651_t1_common change causes tst-fnmatch
to regress with:
422: fnmatch ("[a-z]", "A", 0) = 0 (FAIL, expected FNM_NOMATCH) ***
...
425: fnmatch ("[A-Z]", "z", 0) = 0 (FAIL, expected FNM_NOMATCH) ***

2 files changed, 89 insertions, 44 deletions

diff --git a/posix/tst-fnmatch.input b/posix/tst-fnmatch.input
index 589fb2a940..dc2ca8d01a 100644
--- a/posix/tst-fnmatch.input
+++ b/posix/tst-fnmatch.input
@@ -23,6 +23,63 @@
 # wording describing the situations to be tested.  It does not specify
 # any specific tests.  I.e., the tests below are in no case sufficient.
 # They are hopefully necessary, though.
+#
+# See:
+#
+# http://pubs.opengroup.org/onlinepubs/9699919799/xrat/V4_xbd_chap09.html
+#
+# > RE Bracket Expression
+# >
+# > Range expressions are, historically, an integral part of REs.
+# > However, the requirements of "natural language behavior" and
+# > portability do conflict. In the POSIX locale, ranges must be treated
+# > according to the collating sequence and include such characters that
+# > fall within the range based on that collating sequence, regardless
+# > of character values. In other locales, ranges have unspecified behavior.
+# > ...
+# > The current standard leaves unspecified the behavior of a range
+# > expression outside the POSIX locale. This makes it clearer that
+# > conforming applications should avoid range expressions outside the
+# > POSIX locale, and it allows implementations and compatible user-mode
+# > matchers to interpret range expressions using native order, CEO,
+# > collation sequence, or other, more advanced techniques. The concerns
+# > which led to this change were raised in IEEE PASC interpretation
+# > 1003.2 #43 and others, and related to ambiguities in the
+# > specification of how multi-character collating elements should be
+# > handled in range expressions. These ambiguities had led to multiple
+# > interpretations of the specification, in conflicting ways, which led
+# > to varying implementations. As noted above, efforts were made to
+# > resolve the differences, but no solution has been found that would
+# > be specific enough to allow for portable software while not
+# > invalidating existing implementations.
+#
+# Therefore, using [a-z] does not make much sense except in the C/POSIX locale.
+# The new iso14651_t1_common lists upper case and lower case Latin characters
+# in a different order than the old one which causes surprising results
+# for example in the de_DE locale: [a-z] now includes A because A comes
+# after a in iso14651_t1_common but does not include Z because that comes
+# after z in iso14651_t1_common.
+#
+# This lead to several bugs and problems with user scripts that do not
+# expect [a-z] to match uppercase characters.
+#
+# See the following bugs:
+# https://sourceware.org/bugzilla/show_bug.cgi?id=23393
+# https://sourceware.org/bugzilla/show_bug.cgi?id=23420
+#
+# No consensus exists on how best to handle the changes so the
+# iso14651_t1_common collation element order (CEO) has been changed to
+# deinterlace the a-z and A-Z regions.
+#
+# With the deinterlacing commit ac3a3b4b0d561d776b60317d6a926050c8541655
+# could be reverted to re-test the correct non-interleaved expectations.
+#
+# Please note that despite the region being deinterlaced, the ordering
+# of collation remains the same.  In glibc we implement CEO and because of
+# that we can reorder the elements to reorder ranges without impacting
+# collation which depends on weights.  The collation element ordering
+# could have been changed to include just a-z, A-Z, and 0-9 in three
+# distinct blocks, but this needs more discussion by the community.
 
 # B.6 004(C)
 C		 "!#%+,-./01234567889"	"!#%+,-./01234567889"  0
@@ -418,47 +475,21 @@ C		"-"			"[Z-\\]]"	       NOMATCH
 # Following are tests outside the scope of IEEE 2003.2 since they are using
 # locales other than the C locale.  The main focus of the tests is on the
 # handling of ranges and the recognition of character (vs bytes).
-#
-# See:
-#
-# http://pubs.opengroup.org/onlinepubs/7908799/xbd/re.html
-#
-# > A range expression represents the set of collating elements that fall
-# > between two elements in the current collation sequence,
-# > inclusively. It is expressed as the starting point and the ending
-# > point separated by a hyphen (-).
-# >
-# > Range expressions must not be used in portable applications because
-# > their behaviour is dependent on the collating sequence. Ranges will be
-# > treated according to the current collating sequence, and include such
-# > characters that fall within the range based on that collating
-# > sequence, regardless of character values. This, however, means that
-# > the interpretation will differ depending on collating sequence. If,
-# > for instance, one collating sequence defines ä as a variant of a,
-# > while another defines it as a letter following z, then the expression
-# > [ä-z] is valid in the first language and invalid in the second.
-#
-# Therefore, using [a-z] does not make much sense except in the C/POSIX locale.
-# The new iso14651_t1_common lists upper case and lower case Latin characters
-# in a different order than the old one which causes surprising results
-# for example in the de_DE locale: [a-z] now includes A because A comes
-# after a in iso14651_t1_common but does not include Z because that comes
-# after z in iso14651_t1_common.
 de_DE.ISO-8859-1 "a"			"[a-z]"		       0
 de_DE.ISO-8859-1 "z"			"[a-z]"		       0
 de_DE.ISO-8859-1 "ä"			"[a-z]"		       0
 de_DE.ISO-8859-1 "ö"			"[a-z]"		       0
 de_DE.ISO-8859-1 "ü"			"[a-z]"		       0
-de_DE.ISO-8859-1 "A"			"[a-z]"		       0 # surprising but correct!
+de_DE.ISO-8859-1 "A"			"[a-z]"		       NOMATCH
 de_DE.ISO-8859-1 "Z"			"[a-z]"		       NOMATCH
-de_DE.ISO-8859-1 "Ä"			"[a-z]"		       0 # surprising but correct!
-de_DE.ISO-8859-1 "Ö"			"[a-z]"		       0 # surprising but correct!
-de_DE.ISO-8859-1 "Ü"			"[a-z]"		       0 # surprising but correct!
+de_DE.ISO-8859-1 "Ä"			"[a-z]"		       NOMATCH
+de_DE.ISO-8859-1 "Ö"			"[a-z]"		       NOMATCH
+de_DE.ISO-8859-1 "Ü"			"[a-z]"		       NOMATCH
 de_DE.ISO-8859-1 "a"			"[A-Z]"		       NOMATCH
-de_DE.ISO-8859-1 "z"			"[A-Z]"		       0 # surprising but correct!
-de_DE.ISO-8859-1 "ä"			"[A-Z]"		       0 # surprising but correct!
-de_DE.ISO-8859-1 "ö"			"[A-Z]"		       0 # surprising but correct!
-de_DE.ISO-8859-1 "ü"			"[A-Z]"		       0 # surprising but correct!
+de_DE.ISO-8859-1 "z"			"[A-Z]"		       NOMATCH
+de_DE.ISO-8859-1 "ä"			"[A-Z]"		       NOMATCH
+de_DE.ISO-8859-1 "ö"			"[A-Z]"		       NOMATCH
+de_DE.ISO-8859-1 "ü"			"[A-Z]"		       NOMATCH
 de_DE.ISO-8859-1 "A"			"[A-Z]"		       0
 de_DE.ISO-8859-1 "Z"			"[A-Z]"		       0
 de_DE.ISO-8859-1 "Ä"			"[A-Z]"		       0
@@ -536,21 +567,31 @@ de_DE.ISO-8859-1 "ba"			"[[.a.]]a"	       NOMATCH
 
 
 # And with a multibyte character set.
+en_US.UTF-8	 "a"			"[a-z]"		       0
+en_US.UTF-8	 "z"			"[a-z]"		       0
+en_US.UTF-8	 "A"			"[a-z]"		       NOMATCH
+en_US.UTF-8	 "Z"			"[a-z]"		       NOMATCH
+en_US.UTF-8	 "a"			"[A-Z]"		       NOMATCH
+en_US.UTF-8	 "z"			"[A-Z]"		       NOMATCH
+en_US.UTF-8	 "A"			"[A-Z]"		       0
+en_US.UTF-8	 "Z"			"[A-Z]"		       0
+en_US.UTF-8	 "0"			"[0-9]"		       0
+en_US.UTF-8	 "9"			"[0-9]"		       0
 de_DE.UTF-8	 "a"			"[a-z]"		       0
 de_DE.UTF-8	 "z"			"[a-z]"		       0
 de_DE.UTF-8	 "ä"			"[a-z]"		       0
 de_DE.UTF-8	 "ö"			"[a-z]"		       0
 de_DE.UTF-8	 "ü"			"[a-z]"		       0
-de_DE.UTF-8	 "A"			"[a-z]"		       0 # surprising but correct!
+de_DE.UTF-8	 "A"			"[a-z]"		       NOMATCH
 de_DE.UTF-8	 "Z"			"[a-z]"		       NOMATCH
-de_DE.UTF-8	 "Ä"			"[a-z]"	       0 # surprising but correct!
-de_DE.UTF-8	 "Ö"			"[a-z]"	       0 # surprising but correct!
-de_DE.UTF-8	 "Ü"			"[a-z]"	       0 # surprising but correct!
+de_DE.UTF-8	 "Ä"			"[a-z]"		       NOMATCH
+de_DE.UTF-8	 "Ö"			"[a-z]"		       NOMATCH
+de_DE.UTF-8	 "Ü"			"[a-z]"		       NOMATCH
 de_DE.UTF-8	 "a"			"[A-Z]"		       NOMATCH
-de_DE.UTF-8	 "z"			"[A-Z]"		       0 # surprising but correct!
-de_DE.UTF-8	 "ä"			"[A-Z]"	       0 # surprising but correct!
-de_DE.UTF-8	 "ö"			"[A-Z]"	       0 # surprising but correct!
-de_DE.UTF-8	 "ü"			"[A-Z]"	       0 # surprising but correct!
+de_DE.UTF-8	 "z"			"[A-Z]"		       NOMATCH
+de_DE.UTF-8	 "ä"			"[A-Z]"		       NOMATCH
+de_DE.UTF-8	 "ö"			"[A-Z]"		       NOMATCH
+de_DE.UTF-8	 "ü"			"[A-Z]"		       NOMATCH
 de_DE.UTF-8	 "A"			"[A-Z]"		       0
 de_DE.UTF-8	 "Z"			"[A-Z]"		       0
 de_DE.UTF-8	 "Ä"			"[A-Z]"		       0
diff --git a/posix/tst-regexloc.c b/posix/tst-regexloc.c
index 7fbc496d0c..3ed3b68a1a 100644
--- a/posix/tst-regexloc.c
+++ b/posix/tst-regexloc.c
@@ -29,8 +29,12 @@ do_test (void)
 
   if (setlocale (LC_ALL, "de_DE.ISO-8859-1") == NULL)
     puts ("cannot set locale");
-  else if (regcomp (&re, "[abcdef]*", 0) != REG_NOERROR)
-    puts ("cannot compile expression \"[abcdef]*\"");
+  /* Range expressions in non-POSIX locales are unspecified, but
+     for now in glibc we maintain lowercase/uppercase distinction
+     in our collation element order (but not in collation weights
+     which means strcoll_l still collates as expected).  */
+  else if (regcomp (&re, "[a-f]*", 0) != REG_NOERROR)
+    puts ("cannot compile expression \"[a-f]*\"");
   else if (regexec (&re, "abcdefCDEF", 1, mat, 0) == REG_NOMATCH)
     puts ("no match");
   else