# Since Ruby 3.2 the regex engine remembers which positions it has already tried
# in which state, so the textbook exponential pattern runs in linear time.
# A backreference switches that off; a timeout is the other guard.
def row(code, value) = puts("  #{code.ljust(46)} #{value}")

evil = /^(a|a)*$/
row "Regexp.linear_time?(/^(a|a)*$/)", Regexp.linear_time?(evil)
row '/^(a|a)*$/ =~ "a" * 5000 + "b"', (evil =~ "a" * 5_000 + "b").inspect
puts

backref = /^(a|a)*\1$/
row 'Regexp.linear_time?(/^(a|a)*\1$/)', Regexp.linear_time?(backref)
row "Regexp.timeout (the process-wide limit)", Regexp.timeout.inspect
guarded = Regexp.new(backref.source, timeout: 0.5)
begin
  guarded.match?("a" * 40 + "b")
  row "Regexp.new(..., timeout: 0.5), 40 a's and b", "finished"
rescue Regexp::TimeoutError => e
  row "Regexp.new(..., timeout: 0.5), 40 a's and b", "#{e.class}: #{e.message}"
end