Unexpected regex behaviour

Unexpected regex behaviour

[Robert Högberg]

[-- Attachment #1.1: Type: text/plain, Size: 1195 bytes --]

Hi,

I've noticed that the musl regex implementation behaves slightly
differently than the glibc implementation. I'm attaching a short program
showing the behaviour.

The difference makes yate (http://yate.null.ro) misbehave when running with
musl (reported here: https://github.com/openwrt/telephony/issues/378).

Yate uses a regexp like this:
"^\\([[:alpha:]][[:alnum:]]\\+:\\)\\?/\\?/\\?\\([^[:space:][:cntrl:]@]\\+@\\)\\?\\([[:alnum:]._+-]\\+\\|[[][[:xdigit:].:]\\+[]]\\)\\(:[0-9]\\+\\)\\?"

.. to parse strings like:
"sip:012345678@11.111.11.111:5060;user=phone"

.. and the matches produced by musl are:
Match 0:  0 - 32        sip:012345678@11.111.11.111:5060
Match 1: -1 - -1
Match 2:  0 - 14        sip:012345678@
Match 3: 14 - 27        11.111.11.111
Match 4: 27 - 32        :5060

.. while glibc produces:
Match 0:  0 - 32        sip:012345678@11.111.11.111:5060
Match 1:  0 -  4        sip:
Match 2:  4 - 14        012345678@
Match 3: 14 - 27        11.111.11.111
Match 4: 27 - 32        :5060

What do you think?

I've only tested musl 1.1.19. Sorry if this is not valid for later
releases. I skimmed the 1.1.20 release notes and didn't find anything regex
related.

Regards
Robert

[-- Attachment #1.2: Type: text/html, Size: 1973 bytes --]

[-- Attachment #2: yate_regexp.c --]
[-- Type: text/x-csrc, Size: 1402 bytes --]

#include <regex.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
  const char* s = "sip:012345678@11.111.11.111:5060;user=phone";
  const char* re = "^\\([[:alpha:]][[:alnum:]]\\+:\\)\\?/\\?/\\?\\([^[:space:][:cntrl:]@]\\+@\\)\\?\\([[:alnum:]._+-]\\+\\|[[][[:xdigit:].:]\\+[]]\\)\\(:[0-9]\\+\\)\\?";

  regex_t* data = (regex_t*)malloc(sizeof(regex_t));
  regcomp(data, re, 0);

  const int MAX_MATCH = 9;
  regmatch_t rmatch[MAX_MATCH];
  regexec(data, s, MAX_MATCH, rmatch, 0);

  for (int i = 0; i < MAX_MATCH; i++) {
    char substr[256];
    unsigned substr_len = rmatch[i].rm_eo - rmatch[i].rm_so;
    memcpy(substr, s + rmatch[i].rm_so, substr_len);
    substr[substr_len] = '\0';
    printf("Match %u: %2d - %2d \t%s\n",
           i, rmatch[i].rm_so, rmatch[i].rm_eo,
           substr_len > 0? substr : "");
  }

  return 0;
}


/*
glibc:

Match 0:  0 - 32        sip:012345678@11.111.11.111:5060
Match 1:  0 -  4        sip:
Match 2:  4 - 14        012345678@
Match 3: 14 - 27        11.111.11.111
Match 4: 27 - 32        :5060
Match 5: -1 - -1
Match 6: -1 - -1
Match 7: -1 - -1
Match 8: -1 - -1


musl 1.1.19:
Match 0:  0 - 32        sip:012345678@11.111.11.111:5060
Match 1: -1 - -1
Match 2:  0 - 14        sip:012345678@
Match 3: 14 - 27        11.111.11.111
Match 4: 27 - 32        :5060
Match 5: -1 - -1
Match 6: -1 - -1
Match 7: -1 - -1
Match 8: -1 - -1

*/

Re: Unexpected regex behaviour

[Rich Felker]

On Mon, Oct 29, 2018 at 11:26:19PM +0100, Robert Högberg wrote:
> Hi,
> 
> I've noticed that the musl regex implementation behaves slightly
> differently than the glibc implementation. I'm attaching a short program
> showing the behaviour.
> 
> The difference makes yate (http://yate.null.ro) misbehave when running with
> musl (reported here: https://github.com/openwrt/telephony/issues/378).
> 
> Yate uses a regexp like this:
> "^\\([[:alpha:]][[:alnum:]]\\+:\\)\\?/\\?/\\?\\([^[:space:][:cntrl:]@]\\+@\\)\\?\\([[:alnum:]._+-]\\+\\|[[][[:xdigit:].:]\\+[]]\\)\\(:[0-9]\\+\\)\\?"
> 
> ... to parse strings like:
> "sip:012345678@11.111.11.111:5060;user=phone"
> 
> ... and the matches produced by musl are:
> Match 0:  0 - 32        sip:012345678@11.111.11.111:5060
> Match 1: -1 - -1
> Match 2:  0 - 14        sip:012345678@
> Match 3: 14 - 27        11.111.11.111
> Match 4: 27 - 32        :5060
> 
> ... while glibc produces:
> Match 0:  0 - 32        sip:012345678@11.111.11.111:5060
> Match 1:  0 -  4        sip:
> Match 2:  4 - 14        012345678@
> Match 3: 14 - 27        11.111.11.111
> Match 4: 27 - 32        :5060
> 
> What do you think?
> 
> I've only tested musl 1.1.19. Sorry if this is not valid for later
> releases. I skimmed the 1.1.20 release notes and didn't find anything regex
> related.

I haven't checked which of the extensions you're using are supported
in musl, but the above is not a conforming POSIX BRE. It would be a
lot more readable and portable to use POSIX ERE (REG_EXTENDED) which
has the +, ?, and | operators as standard features. This looks like it
should work:

"^([[:alpha:]][[:alnum:]]+:)?/?/?([^[:space:][:cntrl:]@]+@)?([[:alnum:]._+-]+|[[][[:xdigit:].:]+[]])(:[0-9]+)?"

The only reason to use POSIX BRE is if you need backreferences, which
are not regular and explicitly not supported in ERE.

Rich

Re: Unexpected regex behaviour

[Szabolcs Nagy]

* Rich Felker <dalias@libc.org> [2018-10-29 18:59:57 -0400]:
> On Mon, Oct 29, 2018 at 11:26:19PM +0100, Robert Högberg wrote:
> > Hi,
> > 
> > I've noticed that the musl regex implementation behaves slightly
> > differently than the glibc implementation. I'm attaching a short program
> > showing the behaviour.
> > 
> > The difference makes yate (http://yate.null.ro) misbehave when running with
> > musl (reported here: https://github.com/openwrt/telephony/issues/378).
> > 
> > Yate uses a regexp like this:
> > "^\\([[:alpha:]][[:alnum:]]\\+:\\)\\?/\\?/\\?\\([^[:space:][:cntrl:]@]\\+@\\)\\?\\([[:alnum:]._+-]\\+\\|[[][[:xdigit:].:]\\+[]]\\)\\(:[0-9]\\+\\)\\?"
> > 
> > ... to parse strings like:
> > "sip:012345678@11.111.11.111:5060;user=phone"
> > 
> > ... and the matches produced by musl are:
> > Match 0:  0 - 32        sip:012345678@11.111.11.111:5060
> > Match 1: -1 - -1
> > Match 2:  0 - 14        sip:012345678@
> > Match 3: 14 - 27        11.111.11.111
> > Match 4: 27 - 32        :5060
> > 
> > ... while glibc produces:
> > Match 0:  0 - 32        sip:012345678@11.111.11.111:5060
> > Match 1:  0 -  4        sip:
> > Match 2:  4 - 14        012345678@
> > Match 3: 14 - 27        11.111.11.111
> > Match 4: 27 - 32        :5060
> > 
> > What do you think?
> > 
> > I've only tested musl 1.1.19. Sorry if this is not valid for later
> > releases. I skimmed the 1.1.20 release notes and didn't find anything regex
> > related.
> 
> I haven't checked which of the extensions you're using are supported
> in musl, but the above is not a conforming POSIX BRE. It would be a
> lot more readable and portable to use POSIX ERE (REG_EXTENDED) which
> has the +, ?, and | operators as standard features. This looks like it
> should work:
> 
> "^([[:alpha:]][[:alnum:]]+:)?/?/?([^[:space:][:cntrl:]@]+@)?([[:alnum:]._+-]+|[[][[:xdigit:].:]+[]])(:[0-9]+)?"
> 
> The only reason to use POSIX BRE is if you need backreferences, which
> are not regular and explicitly not supported in ERE.

rewriting it as ERE should not change the grouping behaviour
(\+, \? and \| are non-standard extensions in BRE, but we
support those and the same engine is used as for ERE)

the problem is that the string can be divided in multiple
ways into groups to match the pattern, in such cases
posix requires that the left-most pattern should match
longest, which does not seem to work in musl.

i think neither musl nor glibc gets this right at all
times, but i think this is a simple case that should work.

simpler example (musl busybox sed):

$ echo 'sip:0123' |sed -r 's,^(sip:)?(.+)?,1=\1\n2=\2\n,'
1=sip:
2=0123

$ echo 'sip:0123' |sed -r 's,^(sip:)?/?(.+)?,1=\1\n2=\2\n,'
1=
2=sip:0123

$ echo 'sip:0123' |sed -r 's,^(sip:)?/*(.+)?,1=\1\n2=\2\n,'
1=
2=sip:0123

in all cases \1 should match sip:, but somehow .+ wins when
there is a subpattern with empty match in the middle.