gsub lookahead cannot allocate memory

[stoat1]

Describe the bug
When using regex lookahead jq freezes, eats up all system memory, prints an error message and eventually aborts

To Reproduce

$ jq -n '"qux" | gsub("(?<=u)"; "u")'
"quux"

$ free -g
              total        used        free      shared  buff/cache   available
Mem:             15           5           6           0           3           8
Swap:             1           0           1

$ jq -n '"qux" | gsub("(?=u)"; "u")'
error: cannot allocate memory
[1]    123456 abort (core dumped)  jq -n '"qux" | gsub("(?=u)";  #"u")'

Expected behavior
jq outputs the result and exit

Environment

• Ubuntu 20.04.2 LTS
• jq-1.6

Additional context
I'm aware that this may be an issue in Oniguruma but I wasn't able to reproduce it due to my lack of experience with C

[pkoppstein]

TL;DR: jq -n '"a"|gsub("^";"")' and similar expressions (success without matching any actual characters) cause an infinite loop.

(1) The example you gave (using "(<=u)" involves a look-behind RE. Using it, I was not able to reproduce the problem on a Mac OS, though it's interesting that gojq doesn't like the RE at all, and prints it out in a curious way. Details are below.

(2) gsub("(?=u)"; "u") does present problems for both jq and gojq, though for different reasons. jq goes into an infinite loop, as it does for all expressions like gsub("^";""). It handles sub("(?=u)"; "u") properly. Rightly or wrongly, with regard to gsub, jq tends to take the caveat emptor view, the point being that jq's gsub does not check for quiescence.

Details for look-behind:

for jq in jq1.5 jq1.6 jqMaster gojqMaster ; do
     $jq --version
    echo gsub
    $jq -n '"qux" | gsub("(?<=u)"; "u")'
    echo sub
    $jq -n '"qux" | sub("(?<=u)"; "u")'
    echo
done

Output:

jq-1.5
gsub
"quux"
sub
"quux"

jq-1.6
gsub
"quux"
sub
"quux"

jq-1.6-129-g80052e5-dirty
gsub
"quux"
sub
"quux"

gojq 0.12.5 (rev: 4ada50f/go1.17)
gsub
gojq: invalid regular expression "(?P<=u)": error parsing regexp: invalid named capture: `(?P<=u)`
sub
gojq: invalid regular expression "(?P<=u)": error parsing regexp: invalid named capture: `(?P<=u)`

[stoat1]

@pkoppstein thank you for your findings.

I'd like to add that the same regex works as expected in tools using another regex flavor, e.g.

$ awk 'gsub("^", "")' <<<a
a

jshell> "a".replaceAll("^", "")
$1 ==> "a"

> console.log('a'.replaceAll(/^/g, ''))
a

$ python -c '
import re
print(re.sub("^", "", "a"))
'
a