Regex: is this a Vim bug or my bug?

Question

I have a syn match item like this:

syn match txr_num "[+\-]\?\([0-9]\|[0-9][,0-9]*[0-9]\)\?[.]\([0-9]\|[0-9][,0-9]*[0-9]\)\([eE][+\-]\?[0-9]\+\)\?"

Given an input like 1.234e13 it matches only one digit after the decimal point, causing only 1.2 to be colored, regardless of what combination of digits, commas or e or E exponent follows that 1.2.

If I remove the following underlined part of the regex, it handles that case fine; all of 1.234e13 is colored:

syn match txr_num "[+\-]\?\([0-9]\|[0-9][,0-9]*[0-9]\)\?[.]\([0-9]\|[0-9][,0-9]*[0-9]\)\([eE][+\-]\?[0-9]\+\)\?"
                                                             ^^^^^^^

The subexpression there is this (using more readable regex syntax):

\([0-9]\|[0-9][,0-9]*[0-9]\)
  ^^^^^^^

This matches either a single digit, or else a digit, followed by a any mixture of digits and periods (including empty) and a digit.

Exactly the same pattern is found before the [.], and on that side it works; for instance in the case 123.456, the 123.4 part is matched.

Somehow, Vim's regex is getting stuck on that underlined term. If it is included, it's as if that whole subexpression is just matching a single [0-9], ignoring the branch which matches two or more digits, possibly with interior separating commas.

Am I doing something wrong in that expression anywhere? This is Vim 8.0 on Ubuntu 18.

Update:

Workaround found. It goes away when I exchange the terms of the | branch:

\([0-9]\|[0-9][,0-9]*[0-9]\)   ->   \([0-9][,0-9]*[0-9]\|[0-9]\)

Does Vim's regex branch operator some special ordering semantics such that A|B is not always the same as B|A, or is this a bug?

Answer 1

Obviously, this is your bug.

Why so? Well, let's suppose we have input of 12.34. The "left" expression could match "one" only, but then it can't match "dot". So the engine steps back and re-matches "twelve" and then also "dot" successfully. Then "right" expression matches "three" and... that's all. No one will care of "four", as only "three" was enough to do the job.

Answer 2

The way I am viewing it :

You have 3 optional Parts with 2 non-optional Parts in the middle.

SIGN - INITIAL DIGITS before DOT - [[ DOT - DIGITS after DOT ]] - EXPONENT

Here the Parts in [[ - ]] are non-optional.

DOT is not the Issue.

The DIGITS after DOT :
\([0-9]\|[0-9][,0-9]*[0-9]\)

This has (A|B) where A matches Single DIGIT & B matches multiple Digits.

It is matching the Single DIGIT & moving on to the EXPONENT , which is not there but that is optional.

It is working correctly , but the way to settle your Issue is to make it match all DIGITS (using a +) before moving to the EXPONENT :
\([0-9]+\|[0-9][,0-9]*[0-9]\)

I think this will work.

Alternative Solution :

When (A|B) matches A & the Engine moves on , it has only the optional EXPONENT Part , hence it never comes back to try B , which suggests this Alternative Solution :
At the End of the regex , after the EXPONENT , try to include some non-optional Part , eg (SPACE|Letter-Other-than-E|END-of-line) , which will either match together with A or together with B , in which case the Engine has to come back to that Point.

You could even use both the Solutions together !

Answer 3

It turns out that Vim has uses procedural logic for matching branches, whereby if the left side of the | operator matches, the right is ignored.

It is like effectively like a case statement. If overlapping cases occur in a case statement, the order matters; if a superset match occurs first (.e.g. "match all inputs starting with a) before a subset of that ("match all inputs starting with "abc"`), then the second case never occurs:

if (starts_with("a", string)) {
   // taken for "abc..." strings
} else if (starts_with("abc", string)) {
   // thus, dead code
}

I don't see any issues when the expression is reordered:

\([0-9]\|[0-9][,0-9]*[0-9]\)   ->   \([0-9][,0-9]*[0-9]\|[0-9]\)

The expression is inserted by code generation, which defines it in one place, so I fixed in all places where it occurs, whether necessary or not.

It doesn't seem like a huge issue in an editor; I've been using nothing but Vim for editing since 1994 and didn't notice. Syntax highlighting can use some complex regular expressions, which are similar to the ones used by the corresponding languages for lexical analysis.