CODEWITHSUNDEEP
c++regexc++11time-complexitystandards
xmllmx
xmllmx

Reputation: 42379

Does std::regex guaranttee the time-complexity in worst cases?

The C++ standard [ 30.5.3, n4830 ] defines std::error_complexity to indicate a regex pattern may be too complex to complete.

I just wonder:

Does std::regex guaranttee the time-complexity in worst cases?

Upvotes: 3

Views: 344

Answers (1)

Emma
Emma

Reputation: 27743

It seems it does consider the time complexity, however I doubt that it'd be based on any theoretical worst or best case assumptions; it should likely be based on some relative exceeding certain amount of time trade offs, which is referred to here as pre-set level:

/** * The complexity of an attempted match against a regular expression exceeded a pre-set level. */

Reference

  /** The expression contained an invalid collating element name. */
  constexpr error_type error_collate(_S_error_collate);

  /** The expression contained an invalid character class name. */
  constexpr error_type error_ctype(_S_error_ctype);

  /**
   * The expression contained an invalid escaped character, or a trailing
   * escape.
   */
  constexpr error_type error_escape(_S_error_escape);

  /** The expression contained an invalid back reference. */
  constexpr error_type error_backref(_S_error_backref);

  /** The expression contained mismatched [ and ]. */
  constexpr error_type error_brack(_S_error_brack);

  /** The expression contained mismatched ( and ). */
  constexpr error_type error_paren(_S_error_paren);

  /** The expression contained mismatched { and } */
  constexpr error_type error_brace(_S_error_brace);

  /** The expression contained an invalid range in a {} expression. */
  constexpr error_type error_badbrace(_S_error_badbrace);

  /**
   * The expression contained an invalid character range,
   * such as [b-a] in most encodings.
   */
  constexpr error_type error_range(_S_error_range);

  /**
   * There was insufficient memory to convert the expression into a
   * finite state machine.
   */
  constexpr error_type error_space(_S_error_space);

  /**
   * One of <em>*?+{</em> was not preceded by a valid regular expression.
   */
  constexpr error_type error_badrepeat(_S_error_badrepeat);

  /**
   * The complexity of an attempted match against a regular expression
   * exceeded a pre-set level.
   */
  constexpr error_type error_complexity(_S_error_complexity);

  /**
   * There was insufficient memory to determine whether the
   * regular expression could match the specified character sequence.
   */
  constexpr error_type error_stack(_S_error_stack);

Upvotes: 2

Related Questions