Solved bug in regexp? - sed(1), grep(1) and re_format(7)

E

Erichans

It looks like there's a bug in FreeBSD's sed(1), grep(1), more specifically re_format(7), regarding accented characters and [^...] as described in re_format(7):
Code: 
DESCRIPTION
   [...]
       A bracket expression is a list of characters enclosed in	`[]'.  It nor-
       mally  matches  any single character from the list (but see below).  If
       the list	begins with `^', it matches any	single character (but see  be-
       low)  not from the rest of the list.

Can anyone confirm the unexpected behaviours below?

-- Context
Rich (BB code): 
[100] # uname -a
FreeBSD q210 14.1-RELEASE-p5 FreeBSD 14.1-RELEASE-p5 GENERIC amd64
[101] # pkg which /usr/local/bin/ggrep
/usr/local/bin/ggrep was installed by package gnugrep-3.11
[102] # pkg which /usr/local/bin/gsed
/usr/local/bin/gsed was installed by package gsed-4.9
[103] # locale
LANG=C.UTF-8
LC_CTYPE="C.UTF-8"
LC_COLLATE="C.UTF-8"
LC_TIME="C.UTF-8"
LC_NUMERIC="C.UTF-8"
LC_MONETARY="C.UTF-8"
LC_MESSAGES="C.UTF-8"
LC_ALL=

-- Unexpected behaviours in bold:
Rich (BB code): 
[1] # echo '9a' | /usr/bin/sed         -En 's/([^a])(a)/-\1-\2-/p'
-9-a-
[2] # echo '9a' | /usr/local/bin/gsed  -En 's/([^a])(a)/-\1-\2-/p'
-9-a-
[3] # echo '9a' | /usr/bin/grep        -E '[^a]a'
9a
[4] # echo '9a' | /usr/local/bin/ggrep -E '[^a]a'
9a
[5] #
[6] # echo '9â' | /usr/bin/sed        -En 's/([^â])(â)/-\1-\2-/p'
[7] # echo '9â' | /usr/local/bin/gsed -En 's/([^â])(â)/-\1-\2-/p'
-9-â-
[8] # echo 'ââ' | /usr/bin/sed        -En 's/([â])(â)/-\1-\2-/p'
-â-â-
[9] # echo 'ââ' | /usr/local/bin/gsed -En 's/([â])(â)/-\1-\2-/p'
-â-â-
[10] # echo '9â' | /usr/bin/grep        -E '[^â]â'
[11] # echo '9â' | /usr/local/bin/ggrep -E '[^â]â'
9â
[12] #
[13] # echo '9ç' | /usr/bin/sed        -En 's/([^ç])(ç)/-\1-\2-/p'
[14] # echo '9ç' | /usr/local/bin/gsed -En 's/([^ç])(ç)/-\1-\2-/p'
-9-ç-
[15] # echo 'çç' | /usr/bin/sed        -En 's/([ç])(ç)/-\1-\2-/p'
-ç-ç-
[16] # echo 'çç' | /usr/local/bin/gsed -En 's/([ç])(ç)/-\1-\2-/p'
-ç-ç-
[17] # echo '9ç' | /usr/bin/grep        -E '[^ç]ç'
[18] # echo '9ç' | /usr/local/bin/ggrep -E '[^ç]ç'
9ç
[19] #
[20] # echo '9é' | /usr/bin/sed        -En 's/([^é])(é)/-\1-\2-/p'
[21] # echo '9é' | /usr/local/bin/gsed -En 's/([^é])(é)/-\1-\2-/p'
-9-é-
[22] # echo 'éé' | /usr/bin/sed        -En 's/([é])(é)/-\1-\2-/p'
-é-é-
[23] # echo 'éé' | /usr/local/bin/gsed -En 's/([é])(é)/-\1-\2-/p'
-é-é-
[24] # echo '9é' | /usr/bin/grep        -E '[^é]é'
[25] # echo '9é' | /usr/local/bin/ggrep -E '[^é]é'
9é
 
Interesting. Reproducible.

Code: 
pmc@disp:507:1~$ echo '9ä' | LC_COLLATE="de_DE.UTF-8" /usr/bin/grep ä
9ä
pmc@disp:508:1~$ echo '9ä' | LC_COLLATE="de_DE.UTF-8" /usr/bin/grep 'ä'
9ä
pmc@disp:509:1~$ echo '9ä' | LC_COLLATE="de_DE.UTF-8" /usr/bin/grep '[ä]'
9ä
pmc@disp:510:1~$ echo '9ä' | LC_COLLATE="de_DE.UTF-8" /usr/bin/grep -E '[ä]'
9ä
pmc@disp:511:1~$ echo '9ä' | LC_COLLATE="de_DE.UTF-8" /usr/bin/grep -E '.[ä]'
9ä
pmc@disp:512:1~$ echo '9ä' | LC_COLLATE="de_DE.UTF-8" /usr/bin/grep -E '[^d][ä]'
9ä
pmc@disp:513:1~$ echo '9ä' | LC_COLLATE="de_DE.UTF-8" /usr/bin/grep -E '[^ä][ä]'
pmc@disp:515:1~$ echo '9ä' | LC_COLLATE="de_DE.UTF-8" /usr/bin/grep  '[^ä][ä]'
pmc@disp:516:1~$ echo '9ä' | LC_COLLATE="de_DE.UTF-8" /usr/bin/grep  '[^a][ä]'
9ä
pmc@disp:517:1~$ echo '9ä' | LC_COLLATE="de_DE.UTF-8" /usr/bin/grep  '[^ä][ä]'
pmc@disp:518:1~$ echo '9ä' | LC_COLLATE="de_DE.UTF-8" /usr/bin/grep  '[^ä]'
9ä
pmc@disp:519:1~$ echo '9ä' | LC_COLLATE="de_DE.UTF-8" /usr/bin/grep  '[^ä].'
pmc@disp:520:1~$ echo '9ä' | LC_COLLATE="de_DE.UTF-8" /usr/bin/grep  '[^ä][^d]'
pmc@disp:523:1~$ echo 'ä9a' | LC_COLLATE="de_DE.UTF-8" /usr/bin/grep  '[ä][^d]'
ä9a
 
Indeed, looks like every multi-byte character fails in a negated character list. Bug. PR. ;)

Interestingly, no such issue with regular lists, e.g. trying to match ö (C3 B6) with [ä] (C3 A4) fails as expected...
 
the problems comes from
C: 
if (cs->nwides == 1 && cs->nranges == 0 && cs->ntypes == 0 &&
            cs->icase == 0)
in regcomp.c called from
C: 
if ((ch = singleton(cs)) != OUT) {
if you add another utf-8 in the exclusion set or use ignore case it won't fail
first line is 1062 in /usr/src/lib/libc/regex/regcomp.c and the other is 1050 in the same file

Code: 
1601         if (cs->nwides == 1 && cs->nranges == 0 && cs->ntypes == 0 &&
1602             cs->icase == 0)
1603                 return (cs->wides[0]);
this part can be safely removed in my view because it optimizes the corner case with a set with a single non ascii character in it so not much improvement
 
covacat said:
if you add another utf-8 in the exclusion set or use ignore case it won't fail
Click to expand...
Nice catch.
Code: 
[0] # echo '9â' | /usr/bin/sed      -En 's/([^âé])(â)/-\1-\2-/p'
-9-â-
[1] # echo '9â' | /usr/bin/sed      -En 's/([^âX])(â)/-\1-\2-/p'
[2] # echo '9â' | /usr/bin/sed      -En 's/([^â])(â)/-\1-\2-/ip'
-9-â-
[3] # echo '9â' | /usr/bin/sed      -En 's/([^ââ])(â)/-\1-\2-/p'
-9-â-
[4] # echo '9â' | /usr/bin/grep         '[^ââ]â'
9â
Then, option in command lines 3 and 4 seem like a good (temporary) workaround.


covacat said:
first line is 1062 in /usr/src/lib/libc/regex/regcomp.c and the other is 1050 in the same file
Click to expand...
A bit of a digit shuffle ;)
I see: regcomp.c #L1049-L1051:
C: 
	if ((ch = singleton(cs)) != OUT) {	/* optimize singleton sets */
		ordinary(p, ch);
		freeset(p, cs);
and ~1602, regcomp.c #L1585-L1606:
C: 
/*
 - singleton - Determine whether a set contains only one character,
 - returning it if so, otherwise returning OUT.
 */
static wint_t
singleton(cset *cs)
{
	wint_t i, s, n;

	for (i = n = 0; i < NC; i++)
		if (CHIN(cs, i)) {
			n++;
			s = i;
		}
	if (n == 1)
		return (s);
	if (cs->nwides == 1 && cs->nranges == 0 && cs->ntypes == 0 &&
	    cs->icase == 0)
		return (cs->wides[0]);
	/* Don't bother handling the other cases. */
	return (OUT);
}

By the looks of it, this was introduced in stable/5 (~FreeBSD 5.3); commit Jul 12, 2004:
Make regular expression matching aware of multibyte characters.
or
Make regular expression matching aware of multibyte characters.

and with the introduction of:
Code: 
static wint_t
singleton( ...
where its semantics deviated from the non-singleton bracket expression handling. Apart from a minor change in its parameter definition, the singleton function has not changed over some odd 20 years.

Regression testing?​

I'm not experienced in testing and its related framework, but in order to compare the "singleton" versus "non-singleton" bracket expression semantics, it may be useful to test these two (types) against each other:
Code: 
[1] # echo '9â' | /usr/bin/sed      -En 's/([^â])(â)/-\1-\2-/p'
[2] # echo '9â' | /usr/bin/sed      -En 's/([^ââ])(â)/-\1-\2-/p'
-9-â-

___
P.S.
Of the often mentioned duo sed & awk, awk(1) does not have the same defect (most likely does not rely on regcomp.c):
Code: 
[1]  # echo '9â' | awk '/[^â]â/ { print $1 }'
9â
Code: 
[1] # echo '9a' | awk '/[^a]a/ { print $1 }'
9a
 
covacat said:
i saw the fix after i posted. i wonder why it wasn't MFC-ed yet because the fix is rather old
Click to expand...

It happens; random observations:
  • Not marked for MFC, so there's no reminder e-mail
  • No PR, so there's probably not a clear motivating case- yuripv was nice and ported it over
  • regex(3) changes probably should get a good soak time in to make sure we didn't break anything, given how widespread its use is
  • We don't operate in an MFC-by-default kind of mode, so the mentality to follow-up like that isn't always there
 
You must log in or register to reply here.
Back
Top