Method: Regexp.linear_time?

Defined in:
re.c

.linear_time?(re) ⇒ Boolean .linear_time?(string, options = 0) ⇒ Boolean

Returns true if matching against re can be done in linear time to the input string.

Regexp.linear_time?(/re/) # => true

Note that this is a property of the ruby interpreter, not of the argument regular expression. Identical regexp can or cannot run in linear time depending on your ruby binary. Neither forward nor backward compatibility is guaranteed about the return value of this method. Our current algorithm is (*1) but this is subject to change in the future. Alternative implementations can also behave differently. They might always return false for everything.

(*1): doi.org/10.1109/SP40001.2021.00032

Returns:

  • (Boolean) 


4419
4420
4421
4422
4423
4424
4425
4426
4427
4428
4429
4430
 
# File 're.c', line 4419

static VALUE
rb_reg_s_linear_time_p(int argc, VALUE *argv, VALUE self)
{
    struct reg_init_args args;
    VALUE re = reg_extract_args(argc, argv, &args);

    if (NIL_P(re)) {
        re = reg_init_args(rb_reg_alloc(), args.str, args.enc, args.flags);
    }

    return RBOOL(onig_check_linear_time(RREGEXP_PTR(re)));
}