bug#31526: Range [a-z] does not follow collate order from locale.

[Assaf Gordon]

(adding debbugs mailing list, please use "reply all" to
ensure the thread is public and archived).


Hello,

On 22/05/18 07:48 PM, Bize Ma wrote:
>  > 2018-05-19 22:13 GMT-04:00 Assaf Gordon <address@hidden 
>
> Hi!, thanks for your answer, time and detailed references.
>
> In range definitions I believe that there are two goals in conflict:
>
>      - An stable, simple, range description for programmers.
>      - A clear descrition (even if long) for multilanguage users.

Why are they in conflict? users of sed (programmers or not, using
multibyte locale or not) should understand that regex ranges are tricky 
in multibyte locales.

> For a programmer:
>      The old wisdom is that [a-d] should match only `abcd` (in C locale).
>      The usual recommendation is: "do not use other locales".
>      That is making the use of any other locale almost invalid.
>      However, [a-z] may also match many accented (Latin) characters.
>
> For a multi language user:
>      But if other locales are used, as is a must to allow for most 
> languages used
>      on this world, the range has never been clearly defined, much less 
> the order
>      in which a range will match. There are some clues about "collation 
> order" in
>      GNU sed, but it remains unclear as which collation sort order apply 
> to that.
[...]
> Then, the real question is: What order does sed follow?

Exactly because regex ranges in multibyte locales are not well-defined,
the recommendation is not to use them in portable sed scripts.


> **********************************************************************
> 1.- About ASCII character numeric ranges:
>
> Yes, I agree that it may be conceptually unnecessary to give a collation
> order to "punctuation marks".
> However, that it may be "conceptually unnecessary" does not mean that
> such order is "invalid". A practical inplementation may define some
> such order.
> Please understand that the goal of the code above is to show the practical
> result of using some (locale defined) collation order equivalent to what
> is given by the c function strcoll().

exactly - and strcoll() is implemented in glibc (with possible
replacement in gnulib). It is outside the scope of 'sed' to define the
collation order. And the order could change from one operating system
to the other.

> **********************************************************************
> 2.- About using collating order.
>
>  > > It is expected that a range [a-z] will match 'aAbBcCdD…', all lower and
>  > > upper letters.
>  > > But it isn't:
>  >
>  > It should not be "expected". I don't think it is documented to be
>  > so anywhere in GNU programs.
>
> Well, yes, 'info sed', in section `5 Regular Expressions: selecting text`
> sub-section `5.5 Character Classes and Bracket Expressions` include:
>
>      Within a bracket expression, a "range expression" consists of two
>      characters separated by a hyphen.  It matches any single character
>      that sorts between the two characters, inclusive.  In the default
>      C locale, the sorting sequence is the native character order; for
>      example, '[a-d]' is equivalent to '[abcd]'.
>
>  From 'info sed' (not man sed) sub-section `5.9 Locale Considerations`:
>
>      In other locales, the sorting sequence is not specified, and '[a-d]'
>      might be equivalent to '[abcd]' or to '[aBbCcDd]', or it might fail
>      to match any character, or the set of characters that it matches
>      might even be erratic.
>
> So, the `[a-d]` expression match characters that sort between `a` and `d`.
> That is defined above for the C locale. In other locales the sorting is
> "undefined".
>
>
>  > … Both sed's and grep's manuals contain
>  > the following text:
>  >
>  >     In other locales, the sorting sequence is not specified, and ‘[a-d]’
>  >     might be equivalent to ‘[abcd]’ or to ‘[aBbCcDd]’, or it might 
> fail to
>  >     match any character, or the set of characters that it matches might
>  >     even be erratic.
>
> Yes, It is the exact same text that I also quoted above. But all it
> clearly defines is that the order is based on the definition of each
> locale "in some unspecified way". When the locale change, the order
> may also change.
>
>  > 
> https://www.gnu.org/software/sed/manual/sed.html#Multibyte-regexp-character-classes


I'm not sure I understand if are you agreeing with me or not?
It seems (to me) that the text is clear:
In "C/POSIX" locale, regex range [a-d] matches a,b,c,d.
In other locales, it is not well defined (and can match many variations,
depending on your operating system/libc).


> Yes, At the same page, but at Reporting-Bugs, under the heading
>       [a-z] is case insensitive
>
> https://www.gnu.org/software/sed/manual/sed.html#Reporting-Bugs
>
> We can read:
>
>      [a-z] is case insensitive
>      You are encountering problems with locales. POSIX mandates that [a-z]
>      uses the current locale’s collation order – in C parlance, that means
>      using strcoll(3) instead of strcmp(3). Some locales have a case-
>      insensitive collation order, others don’t.
>
> It seems to say: "current locale's collation order" !!

Yes, there is a locale collation order.

It is defined in libc (e.g. glibc, but there are other libc's out 
there), not in sed, and it is not well documented.

It can also change from one locale to the next (see example below).
GNU sed has no way to change/determine it, or document what it is.

>  > Furthermore, in POSIX 2008 standard range expressions are
>  > undefined for locales other than "C/POSIX"
>
> Yes, however: Does undefined also mean invalid, forbidden, banned or 
> illegal?

I should have used a more accurate term: "Unspecified" instead of 
"undefined" (and thank you for quoting Eric Blake's message about it).

Both terms are explained here:
http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap01.html#tag_01_05_07


In this context, saying "unspecified" means that the results are not
specified by the standard. It could work reliably, it could work and
return unexpected results, it might not work.
It does not mean it is forbidden, but it does mean some implementation
can choose to reject such ranges completely and it would not be
considered a violation of POSIX standard.

> At the moment, it is not illegal to use a bracket range in some other 
> locale.
> Such use does not raise any error (or even warning). As it is not 
> illegal, the
> only aspect that remains to be clearly defined is what is the range 
> order that
> we should expect in every other locale than C.

This is exactly the point of saying "unspecified" - there is (currently)
no definition which GNU sed developers can guarantee will always work in
the specified manner.

> Also, We rely everyday on "not specified" behavior (for some spec):
>
> The -E option is not (yet) defined in current POSIX (The Open Group
> Base Specifications Issue 7, 2018 edition) for sed.
> Yes, It is believed that it will be accepted for the next POSIX version.

Technically speaking, the "-E" option is not "unspecified".
It is an extension beyond the current POSIX standard, and GNU programs
have many such extensions.

But there are two strong cases for "-E":
First, there is an extremely high likelihood it will be accepted to the 
next version of the standard.
Second, several other sed implementations (non-gnu) support "-E" with
the same semantics.


> Some elements are undefined in POSIX just to allow implementations to be 
> diverse:
>
> http://pubs.opengroup.org/onlinepubs/9699919799/xrat/V4_xcu_chap02.html
>
>      The results of giving <tilde> with an unknown login name are undefined
>      because the KornShell "˜+" and "˜-" constructs make use of this 
> condition …
>
> Read carefully: undefined because it is used !.
> That is, it is undefined in the spec to allow implementations to resolve in
> practical ways that might be diferent than the specification (or other
> implementations).

While this does not relate directly to sed,
"undefined" here means that according to the POSIX standard,
the described input is *invalid*, and implementations can decide
how they want to handle it.

You are correct in saying that often POSIX says something is
"unspecified" or "undefined" because existing systems have had
their own behavior long before POSIX even existed, and POSIX does
not want to contradict or forbid existing behavior.

> In the same "comment by Eric Blake" we can read this:
>
>      The behavior of [A-z] in en_US.UTF-8 is "unspecified", but _not_ 
> "undefined".

What "unspecified" means is: POSIX standard deems the input *valid*,
but does not force implementations to return specific results.
(had the input been *invalid*, it would be "undefined" instead of 
"unspecified").

[BTW, I welcome corrections and clarifications if the above is
inaccurate].


> Exactly the same I was meaning:  "unspecified", but _not_ "invalid".
>
> And, exactly, what I am asking for: "glibc should document and define 
> this behavior"

I fully support this: it would be beneficial of GLIBC developers to
documented exactly how collation order works in various multibyte
locales.

However, GNU Sed developers have no way to do so.

This issue should be sent to GLIBC developers
(on their mailing list or bug-tracker website).

>  >
>  > > However, the range [a-Z] does match all letters, lower or upper:
>  > >
>  > >     $ printf '%b' $(printf '\\U%x' {32..127}) | sed 's/[^a-Z]//g'
>  > >     ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
>  >
>  > I would recommend avoiding mixing upper-lower case in regex
>  > ranges, as the result might be unexpected. Compare the following:
>
> In the "comment by Eric Blake" we can also read:
>
>      That is, [A-z] is well-defined in the POSIX locale, and in all other
>      locales where A collates before z (which includes en_US.UTF-8)
>
> Again: "[A-z] is well-defined … "

Yes, in "C" locale, the range "[A-z]" means ASCII value 65 ("A")
to ASCII value 122 ("z"). It means the range also includes
backslash (ASCII 92) and underscore (ASCII 95).

But how do you treat range "[a-Z]" ?
This is range ASCII 97 to ASCII 90 ... is an implementation expected
to swap the min/max values, and treat it as ASCII range 90-97 ?
or somehow understand these are letters, and change it to ASCII 65 to 122 ?


Here's a simpler and more obvious case: The range [3-8] is intuitively
clear, but the reverse is not valid:

  $ echo 7 | LC_ALL=C grep '[3-8]'
  7

  $ echo 7 | LC_ALL=C grep '[8-3]'
  grep: Invalid range end


> Frankly, if I were to follow both main recommendations:
>
>      - Any other locale than C is unspecified: do not use them.
>      - Any range that does not match the previously known ranges:
>        "recommend avoiding mixing upper-lower case in regex ranges"
>
> The usefulness of a bracket range is reduced to almost nothing.
> Only C and only either [a-z] or [A-Z].

"Almost nothing" is a strong statement... I would say the following:

1. In "C" locale, where each character is a single byte (and assuming
an ASCII environment) - ranges are very well defined and easy to use,
not just [a-z] [A-Z], but any ASCII value (including octal values, etc.).

2. In multibyte locales, ranges of specific letters (e.g. "[A-D]")
are not well specified and should be avoided in portable scripts.
However, the character classes are very usable in multibyte locale,
and can be used to match all letters or all digits, etc.
Example:

  $ echo "Γειά σου 123" | LC_ALL=en_CA.UTF-8 sed 's/[[:alpha:]]/*/g'
  **** *** 123

3. If you always use the same environment (e.g. always GLIBC, always GNU 
SED, always the same locale) - then it is very likely (but still not 
guaranteed) that the collation order you observe in regex ranges will
remain the same in the future.


> Is it not possible to declare and document what the collation
> order is/should be for other locales?

Again, this is a glibc issue (or any other library that implements
collation order) - outside the scope of SED.


> **********************************************************************
> 3.- Corect exactly how.
>
>  > > If this is the correct way in which sed should work, then, if you 
> please:
>  >
>  > Yes, it is.
>
> Thanks, but: What does it mean exactly?   My opinion in the right.
>
>    - That [a-z] will always mean 'abcdefghijklmnopqrstuvwxyz' in the C 
> locale?. (Yes)

Correct.

>    - That the order in C locale follows the ASCII numeric order?.        
>         (Yes)

Correct.

>    - That no other locale should be used?                                
>         (No?)

Non-C locales can be used if one understands the limitations
as shown above.
Specifically, portable SED scripts should not use regex
ranges in non-C locale.
If you are absolutely certain you will always run your SED scripts
under GLIBC, it is very very likely the collation order you observe
now will remain for a long time.

>    - That the order in any other locale is secret?                      
>          (Yes)

Not "secret" as in someone actively trying to hide it,
but unknown/undocumented because the developers of GLIBC have not
documented it.

>    - That ranges like [A-z] (valid in C) can not be used in other 
> locales?      (No?)

Should not be used in portable SED scripts.

>    - That other ranges like [*-d] (valid in C) are a crazy idea?        
>          (No?)

Instead of "crazy" let's call it "unspecified" - meaning that each 
program can return different results, and there is no single "correct"
result according to the POSIX standard.

In practice, if you always use GLIBC systems, you will very very likely
see the same results every time.

>    - References to collation order in the manuals must be stricken out?  
>         (No?)

I'm not sure I understand this...


> And we have not even started with more characters as they are possible 
> in UNICODE.
[...]
> Yes, there are discussions about what was relevant at the time.
> But none explain in clear simple words what order the characters
> in a bracket range will follow in a locale that is NOT C. (see
> some simple examples above).

Correct - that is not documented anywhere at the moment.

>  > >     - Why does the manual document otherwise?.
>  >
>  > Errors in the manual are always a possibility.
>  > If you spot such an error, or an example showing incorrect
>  > usage/output - please let us know where it is (e.g. a link
>  > to a manual page  / section).
>
> I have provided a couple of points where "collating order" is used.
> But I suspect that those are not mistakes from your point of view and
> that what is missing is a more detailed description of which collating
> order is being used.
That is a good way to describe the issue.

The term "collation order" is defined in POSIX, e.g. here:
http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap07.html#tag_07_03_02

But the actual order (which character comes before/after another) is
left to implementations to decide.

GLIBC is one such implementations, and GLIBC developers have decided
on such order. Sadly they have not documented it well.

Here's an example of glibc's strange behavior (or at least
strange to me, as I found no explanation for it):

In most multibyte UTF-8 locales the punctuation order
differs from ASCII order, but is consistently the same
(e.g. en_CA.UTF-8 and fr_FR.UTF-8).
For some reason, ja_JP.UTF-8 order is more like ASCII.

Compare the following:

  $ printf "%s\n" a A b B "á" "あ" "ひ" . , : - = > in
  $ LC_ALL=C           sort in > out-C
  $ LC_ALL=en_CA.UTF-8 sort in > out-CA
  $ LC_ALL=ja_JP.UTF-8 sort in > out-JA
  $ paste out-C out-CA out-JA
  ,     =       ,
  -     -       -
  .     ,       .
  :     :       :
  =     .       =
  A     あ       A
  B     ひ       B
  a     A       a
  b     a       b
  á     á       あ
  あ     B       ひ
  ひ     b       á


And that is an example of why we simply can not tell you
what is the "correct" order that you'll get, even if it
seems that in all of your testing you see the same order.

Another example:

  $ echo "あáb" | LC_ALL=ja_JP.utf8 sed 's/[a-z]/*/g'
  あá*
  $ echo "あáb" | LC_ALL=en_CA.utf8 sed 's/[a-z]/*/g'
  あ**

(This is at least the case with GLIBC 2.24-11+deb9u3 on Debian 9).

>  > As such, I'm marking this as "not a bug" and closing the ticket,
>  > but discussion can continue by replying to this thread.
>
> I still remain in doubt, at the very minimum.

I hope this helps clears things out, but I'm happy to continue
this discussion if there are other questions.

regards,
 - assaf