• d-bugmail puremagic.com (68/68) Sep 03 2021 https://issues.dlang.org/show_bug.cgi?id=22273

d-bugmail puremagic.com writes:

https://issues.dlang.org/show_bug.cgi?id=22273

          Issue ID: 22273
           Summary: Range violation in compile-time regex
           Product: D
           Version: D2
          Hardware: x86_64
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P1
         Component: phobos
          Assignee: nobody puremagic.com
          Reporter: stephen.bremer emsibg.com

There is a range violation when running the following code on an input of 7,168
or more characters (possibly relevant: 2^13 - 2^10 = 7,168). Of note, the
runtime regex (i.e., auto re = regex(r"-+(a|b)");) works without errors.

import std.regex;

void main()
{
    string line = "------------..."; // This is actually 7,168 (or more) dashes 
    auto re = ctRegex!(`-+(a|b)`);
    line.matchAll(re);
}

$ ./badregex 
core.exception.RangeError /snap/dmd/102/bin/../import/phobos/std/regex/internal/backtracking.d(730):
Range violation
----------------
??:? _d_arrayboundsp [0x55bebee52f81]
??:? pure nothrow  nogc  trusted void
std.regex.internal.backtracking.BacktrackingMatcher!(char,
std.regex.internal.ir.Input!(char).Input).BacktrackingMatcher.stackPop!(uint).stackPop(ref
uint) [0x55bebee41a29]
??:?  trusted bool std.regex.ctRegexImpl!("-+(a|b)",
[]).func(std.regex.internal.backtracking.BacktrackingMatcher!(char,
std.regex.internal.ir.Input!(char).Input).BacktrackingMatcher) [0x55bebee141a8]
??:?  trusted int std.regex.internal.backtracking.BacktrackingMatcher!(char,
std.regex.internal.ir.Input!(char).Input).BacktrackingMatcher.matchImpl()
[0x55bebee32e36]
??:?  trusted int std.regex.internal.backtracking.BacktrackingMatcher!(char,
std.regex.internal.ir.Input!(char).Input).BacktrackingMatcher.matchFinalize()
[0x55bebee32b8b]
??:?  trusted int std.regex.internal.backtracking.BacktrackingMatcher!(char,
std.regex.internal.ir.Input!(char).Input).BacktrackingMatcher.match(std.regex.internal.ir.Group!(ulong).Group[])
[0x55bebee32d46]
??:? void
std.regex.RegexMatch!(immutable(char)[]).RegexMatch.__ctor!(const(std.regex.internal.ir.Regex!(char).Regex)).__ctor(immutable(char)[],
const(std.regex.internal.ir.Regex!(char).Regex)).__lambda3!(std.regex.internal.ir.Group!(ulong).Group[]).__lambda3(std.regex.internal.ir.Group!(ulong).Group[])
[0x55bebee41630]
??:? void
std.regex.internal.ir.SmallFixedArray!(std.regex.internal.ir.Group!(ulong).Group,
3u).SmallFixedArray.mutate(scope void
delegate(std.regex.internal.ir.Group!(ulong).Group[])) [0x55bebee41420]
??:? ref  trusted std.regex.RegexMatch!(immutable(char)[]).RegexMatch
std.regex.RegexMatch!(immutable(char)[]).RegexMatch.__ctor!(const(std.regex.internal.ir.Regex!(char).Regex)).__ctor(immutable(char)[],
const(std.regex.internal.ir.Regex!(char).Regex)) [0x55bebee415f7]
??:?  safe std.regex.RegexMatch!(immutable(char)[]).RegexMatch
std.regex.matchMany!(std.regex.CTRegexWrapper!(char).CTRegexWrapper,
immutable(char)[]).matchMany(immutable(char)[], ref
std.regex.CTRegexWrapper!(char).CTRegexWrapper) [0x55bebee40555]
??:?  safe std.regex.RegexMatch!(immutable(char)[]).RegexMatch
std.regex.matchAll!(immutable(char)[],
std.regex.CTRegexWrapper!(char).CTRegexWrapper).matchAll(immutable(char)[],
std.regex.CTRegexWrapper!(char).CTRegexWrapper) [0x55bebee4043f]
??:? _Dmain [0x55bebee14064]

Tested with:
DMD v2.090.1, v2.096.0, and v2.097.2
Tested with DMD

--