View source for Regexp engine in Qt5

=Regular expression engine in Qt5=

This page summarizes the research for an alternative regular expression engine to be used in [[Qt 5.0]]. The discussion started on the qt5-feedback mailing list, cf.

* http://lists.qt.nokia.com/pipermail/qt5-feedback/2011-September/001004.html
* https://bugreports.qt.nokia.com/browse/QTBUG-20888

==Current issues with QRegExp==

From http://lists.qt.nokia.com/pipermail/qt5-feedback/2011-September/001054.html

===High level issues===

* QRegExp <span class="caps">API</span> is broken (see '''T7''' in Low Level)
* QRegExp is used for QtScript though it does not fullfill the <span class="caps">ECMAS</span>cript specification [http://www.ecma-international.org/publications/standards/Ecma-262.htm <span class="caps">ECMA</span>-262-1999] ''[ecma-international.org]'' . Missing features include
** Non-greedy quantifiers (see page 141 titled “- 129 -”)
** But current implementation of QtScript uses <span class="caps">JSC</span> which uses its own engine anyway, and only use QRegExp in its api as a container.
* Patternist/XPath also needs Regex features not found in QRegExp, including
** Non-greedy quantifiers ( http://www.w3.org/TR/xpath-functions/#regex-syntax )
* Qt Creator might want to offer multi-line Regex search- and replacing later. This cannot be efficient because of '''T6''' described below. GtkSourceView has exactly [http://bugzilla.gnome.org/show_bug.cgi?id=134674#c1 that problem] ''[bugzilla.gnome.org]'' …
* Customer complained about QRegExp (though I don’t see what’s their exact problem):
** ''In their code they have RegExp? for matching emoticons. Unfortunately, they cannot use QRegExp? because of poor support for negative/positive lookahead. As a workaround they are using the <span class="caps">PCRE</span> (Perl Compatible Regular Expressions) library.''
* Public task request:
** Lookbehind ('''T4''') ([http://trolltech.com/developer/task-tracker/index_html?id=217916&method=entry bug 217916] ''[trolltech.com]'')
** Support for <span class="caps">POSIX</span> syntax ([http://trolltech.com/developer/task-tracker/index_html?id=218604&method=entry bug 218604] ''[trolltech.com]'')
** Removing const modifiers ('''T7''') ([http://trolltech.com/developer/task-tracker/index_html?id=219234&method=entry bug 219234] ''[trolltech.com]'', [http://trolltech.com/developer/task-tracker/index_html?id=209041&method=entry bug 209041] ''[trolltech.com]'')
** Non-greedy quantifiers ('''T3''') ([http://trolltech.com/developer/task-tracker/index_html?id=116127&method=entry bug 116127] ''[trolltech.com]'')

===Low Level issues===

* '''T1''': ^ (caret) and $ (dollar) cannot match at each newline
* '''T2''': . (dot) always matches newlines
* '''T3''': lazy/non-greedy/reluctant quantifiers are not supported. this is not to be confused with minimal matching.
* '''T4''': lookbehind is not supported (lookahead is)
* '''T5''': lastIndexIn does not find that last match which indexIn would have found, e.g. lastIndexIn(“abcd”) for pattern “.*” returns 3, not 0
* '''T6''': only linear input is supported, for a text editor like Kate this does not scale
* '''T7''': QRegExp combines matcher and match object, despite the 1:n relation. As a consequence matching with a const QRegExp instance modifies a const object.

=Future=

* It '''must''' be a solid 3rd party engine — don’t want to develop an in-house engine and maintain it.
* QRegExp likely to be moved into its own module in order to keep source compatibility.
* Addresses the above low-level issues (as much as possible).
* (Nice to have) At least the same syntax / features than std::regex

==Proposed libraries==

* [http://www.pcre.org/ <span class="caps">PCRE</span>] ''[pcre.org]''
* “V8”
* [http://userguide.icu-project.org/strings/regexp <span class="caps">ICU</span>] ''[userguide.icu-project.org]''
* [http://www.boost.org/doc/libs/1_47_0/libs/regex/doc/html/index.html Boost.Regex] ''[boost.org]''
* std::regex (new in C++11)
* [http://code.google.com/p/re2/ RE2] ''[code.google.com]''

==Feature matrix==

✘✔

===Supported syntax: Characters===

{| class="infotable line"
!
!
! QRegExp
! <span class="caps">PCRE</span>
! V8
! <span class="caps">ICU</span>
! Boost.Regex
! std::regex
! RE2
|-
! \a
| <span class="caps">BELL</span>
| ✔
| ✔
|
| ✔
|
|
|
|-
! \A
| beginning of input
|
| ✔
|
| ✔
|
|
|
|-
! \b inside a [set]
| <span class="caps">BACKSPACE</span>
| ?
| ✔
|
|
|
|
|
|-
! \b outside a [set]
| on a word boundary
| ✔
| ✔
|
|
|
|
|
|-
! \B
| not on a word boundary
| ✔
| ✔
|
| ✔
|
|
|
|-
! \cX
| <span class="caps">ASCII</span> control character X
| ✘
| ✔
|
| ✔
|
|
|
|-
! \d
| digit
| ✔
| ✔
|
| ✔
|
|
|
|-
! \D
| non digit
| ✔
| ✔
|
| ✔
|
|
|
|-
! \e
| <span class="caps">ESCAPE</span>
| ✘
| ✔
|
| ✔
|
|
|
|-
! \E
| end of \Q … \E quoting
| ✘
| ✔
|
| ✔
|
|
|
|-
! \f
| <span class="caps">FORM</span> <span class="caps">FEED</span>
| ✔
| ✔
|
| ✔
|
|
|
|-
! \G
| end of previous match
| ✘
| ✔
|
| ✔
|
|
|
|-
! \n
| <span class="caps">LINE</span> <span class="caps">FEED</span>
| ✔
| ✔
|
|
|
|
|
|-
! \N{x}
| <span class="caps">UNICODE</span> <span class="caps">CHARACTER</span> <span class="caps">NAME</span> x
| ✘
| ✘
|
| ✔
|
|
|
|-
! \p{x}
| <span class="caps">UNICODE</span> <span class="caps">PROPERTY</span> <span class="caps">NAME</span> x
| ✘
| ✔
|
| ✔
|
|
|
|-
! \P{x}
| <span class="caps">UNICODE</span> <span class="caps">PROPERTY</span> <span class="caps">NAME</span> not x
| ✘
| ✔
|
| ✔
|
|
|
|-
! \Q
| start of \Q … \E quoting
| ✘
| ✔
|
| ✔
|
|
|
|-
! \r
| <span class="caps">CARRIAGE</span> <span class="caps">RETURN</span>
| ✔
| ✔
|
| ✔
|
|
|
|-
! \s
| white space
| ✔
| ✔
|
| ✔
|
|
|
|-
! \S
| non white space
| ✔
| ✔
|
| ✔
|
|
|
|-
! \t
| <span class="caps">HORIZONTAL</span> <span class="caps">TAB</span>
| ✔
| ✔
|
| ✔
|
|
|
|-
! \uhhhh
| U+hhhh (between U+0000 and U+FFFF)
| ✘
| ✘
|
|
|
|
|
|-
! \Uhhhhhhhh
| U+hhhhhhhh (between U+00000000 and U+0010FFFF)
| ✘
| ✘
|
|
|
|
|
|-
! \v
| <span class="caps">VERTICAL</span> <span class="caps">TAB</span>
| ✔
| ✔
|
| ✘
|
|
|
|-
! \w
| word character
| ✔
| ✔
|
| ✔
|
|
|
|-
! \W
| non word character
| ✔
| ✔
|
| ✔
|
|
|
|-
! \x{hhhh}
| U+hhhh
| ✘
| ✔ (0-10FFFF)
|
| ✔ (0-10FFFF)
|
|
|
|-
! \xhhhh
| U+hhhh
| ✔ (0000-<span class="caps">FFFF</span>)
| ✔ (00-FF)
|
| ✔ (00-FF)
|
|
|
|-
! \X
| grapheme cluster
| ✘
| ✘
|
|
|
|
|
|-
! \Z
| end of input (or before the final \n)
| ✘
| ✔
|
| ✔
|
|
|
|-
! \z
| end of input
| ✘
| ✔
|
| ✔
|
|
|
|-
! \n
| n-th backreference
| ✔
| ✔
|
|
|
|
|
|-
! \0ooo
| <span class="caps">ASCII</span>/Latin-1 character 0ooo
| ✔
| ✔
|
|
|
|
|
|-
! .
| any character but newlines
| ✔
| ✔
|
| ✔
|
|
|
|-
! ^
| line beginning
| ✔
| ✔
|
| ✔
|
|
|
|-
! $
| line end
| ✔
| ✔
|
| ✔
|
|
|
|-
! \
| quote the following symbol
| ✔
| ✔
|
| ✔
|
|
|
|-
! [pattern]
| set
| ✔
| ✔
|
| ✔
|
|
|
|}

===Supported syntax: Operators===

{| class="infotable line"
! Operator
!
! QRegExp
! <span class="caps">PCRE</span>
! V8
! <span class="caps">ICU</span>
! Boost.Regex
! std::regex
! RE2
|-
! *
| match 0 or more times
| ✔
| ✔
|
| ✔
| ?
| ?
| ✔
|-
! +
| match 1 or more times
| ✔
| ✔
|
| ✔
|
|
| ✔
|-
! ?
| match 0 or 1 times
| ✔
| ✔
|
| ✔
|
|
| ✔
|-
! {n}
| match n times
| ✔
| ✔
|
| ✔
|
|
| ✔
|-
! {n,}
| match n or more times
| ✔
| ✔
|
| ✔
|
|
| ✔
|-
! {n,m}
| match between n and m times
| ✔
| ✔
|
| ✔
|
|
| ✔
|-
! *?
| match 0 or more times, not greedy
| ✘
| ✔
|
| ✔
|
|
| ✔
|-
! <ins>? </ins>
| match 1 or more times, not greedy
| ✘
| ✔
|
| ✔
|
|
| ✔
|-
! ??
| match 0 or 1 times, not greedy
| ✘
| ✔
|
| ✔
|
|
| ✔
|-
! {n}?
| match n times
| ✘
| ✔
|
| ✔
|
|
| ✔
|-
! {n,}?
| match n or more times, not greedy
| ✘
| ✔
|
| ✔
|
|
| ✔
|-
! {n,m}?
| match between n and m times, not greedy
| ✘
| ✔
|
| ✔
|
|
| ✔
|-
! *
| match 0 or more times, possessive
| ✘
| ✔
|
| ✔
|
|
| ✘
|-
! ++
| match 1 or more times, possessive
| ✘
| ✔
|
| ✔
|
|
| ✘
|-
! ?+
| match 0 or 1 times, possessive
| ✘
| ✔
|
| ✔
|
|
| ✘
|-
! {n}+
| match n times
| ✘
| ✔
|
| ✔
|
|
| ✘
|-
! {n,}+
| match n or more times, possessive
| ✘
| ✔
|
| ✔
|
|
| ✘
|-
! {n,m}+
| match between n and m times, possessive
| ✘
| ✔
|
| ✔
|
|
| ✘
|-
! ( … )
| capturing group
| ✔
| ✔
|
| ✔
|
|
| ✔
|-
! (?: … )
| group
| ✔
| ✔
|
| ✔
|
|
| ✔
|-
! (?&gt; … )
| atomic grouping
| ✘
| ✔
|
| ✔
|
|
| ✘
|-
! (?# … )
| comment
| ✘
| ✔
|
| ✔
|
|
| ✘
|-
! (?= … )
| look-ahead assertion
| ✔
| ✔
|
| ✔
|
|
| ✘
|-
! (?! … )
| negative look-ahead assertion
| ✔
| ✔
|
| ✔
|
|
| ✘
|-
! (?&lt;= … )
| look-behind assertion
| ✘
| ✔
|
| ✔
|
|
| ✘
|-
! (?&lt;! … )
| negative look-behind assertion
| ✘
| ✔
|
| ✔
|
|
| ✘
|-
! (?flags: … )
| flags change
| ✘
| ✔
|
|
|
|
| ✔
|-
! (?flags)
| flags change
| ✘
| ✔
|
| ✔
|
|
| ✔
|-
! (?P&lt;name&gt; …)
| named capturing group
| ✘
| ✔
|
| ✘
|
|
| ✔
|-
! (?&lt;name&gt; …)
| named capturing group
| ✘
| ✔
|
| ✘
|
|
| ✘
|-
! (?‘name’ …)
| named capturing group
| ✘
| ✔
|
| ✘
|
|
| ✘
|-
! (?| …)
| branch reset
| ✘
| ✔
|
| ✘
|
|
| ✘
|-
!
|
|
|
|
|
|
|
|
|-
!
|
|
|
|
|
|
|
|
|}

===Supported syntax: flags===

=Benchmarks=

See https://gitorious.org/qt-regexp-benchmarks/qt-regexp-benchmarks for the code and https://gitorious.org/qt-regexp-benchmarks/pages/Home for some results.

<sup>1</sup> It’s actually not possible to <span class="caps">UNSET</span> /s for QRegExp, i.e. making the dot not to match a newline.

<sup>2</sup> Cf. http://lists.qt.nokia.com/pipermail/qt5-feedback/2011-August/000962.html

===Categories:===

* [[:Category:Developing Qt|Developing_Qt]]
** [[:Category:Developing Qt::Qt-Planning|Qt Planning]]
*** [[:Category:Developing Qt::Qt-Planning::Qt-Public-Roadmap|Qt Public Roadmap]]