Strange regular expressions

[longxya]

Why result of Regex.Match("wtfaab","(.).+()+?b") is the last word "b"? and group1 capture the first word 'w'. It's a feature kind of c#?

[huoyaoyuan]

You can use the source generator to see the implementation of particular regular expression, and explanation. The explanation of (.).+()+?b:

        /// <remarks>
        /// Pattern:<br/>
        /// <code>(.).+()+?b</code><br/>
        /// Explanation:<br/>
        /// <code>
        /// ○ 1st capture group.<br/>
        ///     ○ Match any character other than '\n'.<br/>
        /// ○ Match a character other than '\n' greedily at least once.<br/>
        /// ○ Loop lazily at least once.<br/>
        ///     ○ 2nd capture group.<br/>
        ///         ○ Match an empty string.<br/>
        /// ○ Match 'b'.<br/>
        /// </code>

[DL444]

Smells like bugs or at least behavior inconsistencies that warrant documentation. Reproducible sample:

using System.Text.RegularExpressions;

string input = "Test";
Match matchInterpreted = new Regex(RegexDemo.Pattern, RegexOptions.None).Match(input);
Match matchCompiled = new Regex(RegexDemo.Pattern, RegexOptions.Compiled).Match(input);
Match matchGenerated = RegexDemo.GetRegex().Match(input);

Console.WriteLine($"Interpreted: {matchInterpreted.Value}");
Console.WriteLine($"Compiled: {matchCompiled.Value}");
Console.WriteLine($"Generated: {matchGenerated.Value}");

internal static partial class RegexDemo
{
    [GeneratedRegex(Pattern)]
    public static partial Regex GetRegex();

    public const string Pattern = @"^.*(?:)+?$";
}

Output:

Interpreted: 
Compiled: Test
Generated: Test

Reproducible with .NET 7, 8, and 9; not with .NET 6. Behavior difference likely introduced by the compiled regex rewrite in .NET 7. In .NET 6, the result for the compiled variant matches interpreted (source generation not available with .NET 6). The new behavior looks more reasonable to me.

I found one breaking change notice related to regex for .NET 7, but it seems to cover a different underlying issue.

[elgonzo]

The new behavior looks more reasonable to me.

As far as the compiled/src-gen result is concerned, yes.

The interpreted regex matching is still producing incorrect results regarding empty sub-expressions with quantifiers, and preferably should be fixed to make it produce the same correct result as the compiled/src-gen regex matching.

@huoyaoyuan

You can use the source generator to see the implementation

Where exactly does it explain the observed (and incorrect) matching behavior? You posted a bunch of (auto-generated) code comments that don't explain the observed results.

[elgonzo]

It seems the interpreting engine still has a bug with empty sub-expression in combination with the +? (or the equivalent {1,}?) quantifier.

string input = "ab";

Match m1 = Regex.Match(input, "a()b");
Match m2 = Regex.Match(input, "a()+?b");
Match m3 = Regex.Match(input, "a(){1,}?b");
Match m4 = Regex.Match(input, "a()*?b");
Match m5 = Regex.Match(input, "a(){0,}?b");
Match m6 = Regex.Match(input, "a()+b");
Match m7 = Regex.Match(input, "a()*b");

Console.WriteLine($"{m1.Success} {m1.Value}");
Console.WriteLine($"{m2.Success} {m2.Value}");
Console.WriteLine($"{m3.Success} {m3.Value}");
Console.WriteLine($"{m4.Success} {m4.Value}");
Console.WriteLine($"{m5.Success} {m5.Value}");
Console.WriteLine($"{m6.Success} {m6.Value}");
Console.WriteLine($"{m7.Success} {m7.Value}");

Output using .NET 9 on dotnetfiddle (https://dotnetfiddle.net/WvEuyr):

True ab
True b
True b
True ab
True ab
True ab
True ab

Note how the result using ()+? or (){1,}? in the pattern is incorrect.

EDIT: FYI, the issue seems to be with the interpreting regex engine. The issue does not occur using compiled regex expressions (https://dotnetfiddle.net/405nAA). Couldn't check src-gen, because dotnetfiddle. but i am going to assume based on @DL444 post that src-gen regex matching is okay.

EDIT2: I mistakenly equated (){1,} with ()+?. Which obviously it isn't. (){1,}? is equivalent to ()+?. Edited my post and the dotnetfiddle example accordingly.

A possibly valueable addendum:
Having established that (){1,}? breaks the regex interpreter, a thought came to my mind: What if n in (){n,}? is larger than 1. Well, based on some quick tests on dotnetfiddle, it seems the issue occurs only when n == 1 (i.e., the equivalent to ()+?). The issue does not occur when i for example use (){2,}? or (){100,}? (https://dotnetfiddle.net/zG4TMA)

[longxya]

()+ (){1,} and (){1,2147483647} are equivalent.

The issue does not occur using compiled regex expressions

Using new Regex("(.)(?'2-1'(?'-1'.))", RegexOptions.Compiled).Matches("wtf") will throw an exception "Index was outside the bounds of the array". I believe that the Regex class shouldn't throw an exception when catching an exception other than a pattern error. Therefore, I avoid using compiled regex expressions in my testing tools. In doing so, I discovered the "feature" of ()+?.

I think compiled regular expressions should only affect execution time. Ordinary and compiled regular expressions should yield exactly the same result.
I initially thought it could be used as a feature to offset the match.

So, we could consider it for a bug?

[DL444]

Using new Regex("(.)(?'2-1'(?'-1'.))", RegexOptions.Compiled).Matches("wtf") will throw an exception "Index was outside the bounds of the array".

This is definitely a separate problem, I suggest that you create two separate issues for them.

---

I did some debugging for the first problem. For regex a(?:)+?b, the generated interpreter code is:

{Direction: left-to-right

000000 ~Lazybranch       addr = 13
000002 ~Setmark
000003  One              'a'
000005 ~Setmark
000006 ~Lazybranchmark   addr = 6
000008  One              'b'
000010 ~Capturemark      index = 0
000013  Stop
}

The handing of Lazybranchmark instruction at address 000006 looks fishy. It pushes the index marked by the Setmark at address 000005 to the stack, and this push is never matched with a corresponding pop.

The Capturemark at 000010 handles the capturing of group 0 (i.e. Value). It should pop the index marked by Setmark at 000002, but instead popped the index pushed by Lazybranchmark at 000006. This causes group 0 of the resulting match to erroneously start at where the empty loop began, and explains the current behavior we see.

Not sure how to fix though. Removing the push causes tests failures for some cases, so it's probably not the right thing to do.

it seems the issue occurs only when n == 1

This is because the case where n > 1 is handled by a different pair of instructions, Setcount/Lazybranchcount, which is not affected by the issue.

[longxya]

I did some tests.
It looks like ()+? would make nearest outside brackets start at where the empty loop began, and this effect maybe gradually spread to group 0 or not. For example:
a+(x(.)+()+?)b and (x(.)+()+?)b

Some of the tests behaved so strangely that I don't even know how to describe them. Such as: (?<=(.()+?))x

And for pattern (?'x'a)(a((?'refer'\1)|(?<=(?'pre'a))|(|z))+?a)+, if change the number of 'a's, the transformation of the matching results is very strange.

Perhaps all these strange matches above are due to ()+?, which changes the starting position of the parent bracket to the start of ()+?. Combined with backtracking or greedy matching, it creates a fascinating chemical reaction.