Tips for handling localized ranges in regular expressions

Developers as well as casual grep users are accustomed to using ranges in regular expressions, such as [a-zA-Z] or [0-9]. However, they often don't realize that these regular expressions harbor problems that can lead to unexpected behavior.

This article delves into the issues with using ranges in different locales and the solutions sought by developers of various libraries, including the GNU C Library (glibc).

The problem with regular expression ranges

Under the POSIX standard, a regular expression using a range expression has unspecified behavior in any locale other than the POSIX locale. This locale applies only to programs or environments whose environment variables for the locale (such as LANG or LC_ALL) specify either POSIX or C, or who don't have those environment variables set at all.

Of course, this hardly ever happens. Most people specify their country and language when setting up their system and get a locale such as en_US.UTF-8, in this case, indicating U.S. English with UTF-8 characters.

For most programs and users, therefore, a popular regular expression range such as [a-zA-Z] or [0-9] has undefined and ultimately unreliable behavior. In theory, users should employ bracket expressions such as [[:alpha:]] and [[:digit:]]. In practice, it works as expected in many, but not all, locales.

What should a library do to support developers and make developing applications easier? We will explore current and upcoming solutions in the next sections.

Possible solutions and their relationships to POSIX and Unicode

There are a number of possible solutions. The support for ranges such as [a-zA-Z] in the C (POSIX) locale is a clue that support for the ranges was implemented by early C libraries when ASCII was the norm. Although there are many conflicting solutions, each generally maps to one of the following implementations:

• Native character order (NCO): This means that a developer looking at a code chart for the character set can logically identify all characters in the range by reviewing, in order, those characters in the code chart from the start of the range to the end of the range.
• Collation element order (CEO): This means that a developer looking at the locale sources for the current locale can logically identify all characters in the range by reviewing, in order, those characters in the LC_COLLATE definition in the POSIX locale sources (later compiled into the binary locale on your system, e.g., en_US.UTF-8) from the start of the range to the end of the range.
• Collation sequence order (CSO): This means that a developer looking at, for one definition of a natural language order, a dictionary with said natural language order can logically identify all characters in the range by reviewing, in order, those characters in the dictionary from the start of the range to the end of the range.

For example, in the article Boost C++ POSIX regular extended expression APIs, the authors implemented CSO with an option to fall back to NCO. As another example, the GNU Awk (Gawk) implementation has two modes: a "traditional" mode that emulates NCO within certain ASCII ranges and a POSIX-based mode that emulates CSO. The Boost and Gawk implementations offer a very similar degree of choice between NCO and CSO.

In glibc, the implementation is based on the early POSIX specifications that required CEO. In the built-in C and POSIX locale, the NCO and CEO are equivalent because the ASCII character set order can be ordered the same as the collation elements in the locale source specification. The glibc locale for en_US.UTF-8 makes the NCO and CEO equivalent for lowercase Latin characters, uppercase Latin characters, and numbers in order to preserve developer expectations for sorting these ranges; e.g., lowercase Latin characters are not interleaved with uppercase Latin characters.

CEO and CSO require large element lists and thus add a lot more overhead to implementations than NCO.

The published ISO 14651 (2020) standard, most recently derived from Unicode 13.0.0 (2020), defines the international string ordering and comparison, and glibc uses this standard as the basis for string collation. The collation element ordering in the ISO standard interleaves lowercase and uppercase characters in such a way that CEO is more aligned to logical groups of letters e.g. A and a, instead of NCO. Direct usage of ISO 14651 in glibc caused regressions due to this grouping; e.g., [a-z] would match A unexpectedly.

Current and upcoming solutions

Boost's interface allows one to choose between a logical NCO or CSO (as defined for a single natural language ordering), thus offering two of three solutions listed in the previous section. A user who desires a distinct CEO can create a completely new locale source definition and distribute that to users that want a distinct ordering. Thread-safe locale APIs can be used to set and use the locale on a per-thread basis.

The APIs implemented by the ICU project support many possible CSOs for a given language, including dictionary sort, address book sort, calendar sort, etc. No single CSO will solve the needs of all users.

The glibc implementation of CEO does not meet the needs of developers who are either looking at a code chart or applying common-sense logic to natural language ordering. Migrating glibc from CEO to CSO seems like a logical way forward, but the internal implementation will need to be significantly improved to support this transition. The most straightforward first step is a C.UTF-8 that uses NCO in glibc and avoids the overhead of CEO or CSO.

With the release of glibc 2.35 in February 2022, the project now has an official harmonized and C.UTF-8 that will use NCO for ASCII regular expression ranges and NCO for collation (code-point collation order).

You can already use this new C.UTF-8 locale in Fedora (starting with Fedora 35).  In the future, C.UTF-8 will be extended to allow rational ranges that cover all code points in NCO.