1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtCore module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #include "qregexp.h"

    43 

    44 #include "qalgorithms.h"

    45 #include "qbitarray.h"

    46 #include "qcache.h"

    47 #include "qdatastream.h"

    48 #include "qlist.h"

    49 #include "qmap.h"

    50 #include "qmutex.h"

    51 #include "qstring.h"

    52 #include "qstringlist.h"

    53 #include "qstringmatcher.h"

    54 #include "qvector.h"

    55 #include "private/qfunctions_p.h"

    56 

    57 #include <limits.h>

    58 

    59 QT_BEGIN_NAMESPACE

    60 

    61 int qFindString(const QChar *haystack, int haystackLen, int from,

    62     const QChar *needle, int needleLen, Qt::CaseSensitivity cs);

    63 

    64 // error strings for the regexp parser

    65 #define RXERR_OK         QT_TRANSLATE_NOOP("QRegExp", "no error occurred")

    66 #define RXERR_DISABLED   QT_TRANSLATE_NOOP("QRegExp", "disabled feature used")

    67 #define RXERR_CHARCLASS  QT_TRANSLATE_NOOP("QRegExp", "bad char class syntax")

    68 #define RXERR_LOOKAHEAD  QT_TRANSLATE_NOOP("QRegExp", "bad lookahead syntax")

    69 #define RXERR_REPETITION QT_TRANSLATE_NOOP("QRegExp", "bad repetition syntax")

    70 #define RXERR_OCTAL      QT_TRANSLATE_NOOP("QRegExp", "invalid octal value")

    71 #define RXERR_LEFTDELIM  QT_TRANSLATE_NOOP("QRegExp", "missing left delim")

    72 #define RXERR_END        QT_TRANSLATE_NOOP("QRegExp", "unexpected end")

    73 #define RXERR_LIMIT      QT_TRANSLATE_NOOP("QRegExp", "met internal limit")

    74 #define RXERR_INTERVAL   QT_TRANSLATE_NOOP("QRegExp", "invalid interval")

    75 #define RXERR_CATEGORY   QT_TRANSLATE_NOOP("QRegExp", "invalid category")

    76 

    77 /*

    78   WARNING! Be sure to read qregexp.tex before modifying this file.

    79 */

    80 

    81 /*!

    82     \class QRegExp

    83     \reentrant

    84     \brief The QRegExp class provides pattern matching using regular expressions.

    85 

    86     \ingroup tools

    87     \ingroup shared

    88 

    89     \keyword regular expression

    90 

    91     A regular expression, or "regexp", is a pattern for matching

    92     substrings in a text. This is useful in many contexts, e.g.,

    93 

    94     \table

    95     \row \i Validation

    96          \i A regexp can test whether a substring meets some criteria,

    97          e.g. is an integer or contains no whitespace.

    98     \row \i Searching

    99          \i A regexp provides more powerful pattern matching than

   100          simple substring matching, e.g., match one of the words

   101          \e{mail}, \e{letter} or \e{correspondence}, but none of the

   102          words \e{email}, \e{mailman}, \e{mailer}, \e{letterbox}, etc.

   103      \row \i Search and Replace

   104          \i A regexp can replace all occurrences of a substring with a

   105          different substring, e.g., replace all occurrences of \e{&}

   106          with \e{\&} except where the \e{&} is already followed by

   107          an \e{amp;}.

   108     \row \i String Splitting

   109          \i A regexp can be used to identify where a string should be

   110          split apart, e.g. splitting tab-delimited strings.

   111     \endtable

   112 

   113     A brief introduction to regexps is presented, a description of

   114     Qt's regexp language, some examples, and the function

   115     documentation itself. QRegExp is modeled on Perl's regexp

   116     language. It fully supports Unicode. QRegExp can also be used in a

   117     simpler, \e{wildcard mode} that is similar to the functionality

   118     found in command shells. The syntax rules used by QRegExp can be

   119     changed with setPatternSyntax(). In particular, the pattern syntax

   120     can be set to QRegExp::FixedString, which means the pattern to be

   121     matched is interpreted as a plain string, i.e., special characters

   122     (e.g., backslash) are not escaped.

   123 

   124     A good text on regexps is \e {Mastering Regular Expressions}

   125     (Third Edition) by Jeffrey E. F.  Friedl, ISBN 0-596-52812-4.

   126 

   127     \tableofcontents

   128 

   129     \section1 Introduction

   130 

   131     Regexps are built up from expressions, quantifiers, and

   132     assertions. The simplest expression is a character, e.g. \bold{x}

   133     or \bold{5}. An expression can also be a set of characters

   134     enclosed in square brackets. \bold{[ABCD]} will match an \bold{A}

   135     or a \bold{B} or a \bold{C} or a \bold{D}. We can write this same

   136     expression as \bold{[A-D]}, and an experession to match any

   137     captital letter in the English alphabet is written as

   138     \bold{[A-Z]}.

   139 

   140     A quantifier specifies the number of occurrences of an expression

   141     that must be matched. \bold{x{1,1}} means match one and only one

   142     \bold{x}. \bold{x{1,5}} means match a sequence of \bold{x}

   143     characters that contains at least one \bold{x} but no more than

   144     five.

   145 

   146     Note that in general regexps cannot be used to check for balanced

   147     brackets or tags. For example, a regexp can be written to match an

   148     opening html \c{<b>} and its closing \c{</b>}, if the \c{<b>} tags

   149     are not nested, but if the \c{<b>} tags are nested, that same

   150     regexp will match an opening \c{<b>} tag with the wrong closing

   151     \c{</b>}.  For the fragment \c{<b>bold <b>bolder</b></b>}, the

   152     first \c{<b>} would be matched with the first \c{</b>}, which is

   153     not correct. However, it is possible to write a regexp that will

   154     match nested brackets or tags correctly, but only if the number of

   155     nesting levels is fixed and known. If the number of nesting levels

   156     is not fixed and known, it is impossible to write a regexp that

   157     will not fail.

   158 

   159     Suppose we want a regexp to match integers in the range 0 to 99.

   160     At least one digit is required, so we start with the expression

   161     \bold{[0-9]{1,1}}, which matches a single digit exactly once. This

   162     regexp matches integers in the range 0 to 9. To match integers up

   163     to 99, increase the maximum number of occurrences to 2, so the

   164     regexp becomes \bold{[0-9]{1,2}}. This regexp satisfies the

   165     original requirement to match integers from 0 to 99, but it will

   166     also match integers that occur in the middle of strings. If we

   167     want the matched integer to be the whole string, we must use the

   168     anchor assertions, \bold{^} (caret) and \bold{$} (dollar). When

   169     \bold{^} is the first character in a regexp, it means the regexp

   170     must match from the beginning of the string. When \bold{$} is the

   171     last character of the regexp, it means the regexp must match to

   172     the end of the string. The regexp becomes \bold{^[0-9]{1,2}$}.

   173     Note that assertions, e.g. \bold{^} and \bold{$}, do not match

   174     characters but locations in the string.

   175 

   176     If you have seen regexps described elsewhere, they may have looked

   177     different from the ones shown here. This is because some sets of

   178     characters and some quantifiers are so common that they have been

   179     given special symbols to represent them. \bold{[0-9]} can be

   180     replaced with the symbol \bold{\\d}. The quantifier to match

   181     exactly one occurrence, \bold{{1,1}}, can be replaced with the

   182     expression itself, i.e. \bold{x{1,1}} is the same as \bold{x}. So

   183     our 0 to 99 matcher could be written as \bold{^\\d{1,2}$}. It can

   184     also be written \bold{^\\d\\d{0,1}$}, i.e. \e{From the start of

   185     the string, match a digit, followed immediately by 0 or 1 digits}.

   186     In practice, it would be written as \bold{^\\d\\d?$}. The \bold{?}

   187     is shorthand for the quantifier \bold{{0,1}}, i.e. 0 or 1

   188     occurrences. \bold{?} makes an expression optional. The regexp

   189     \bold{^\\d\\d?$} means \e{From the beginning of the string, match

   190     one digit, followed immediately by 0 or 1 more digit, followed

   191     immediately by end of string}.

   192 

   193     To write a regexp that matches one of the words 'mail' \e or

   194     'letter' \e or 'correspondence' but does not match words that

   195     contain these words, e.g., 'email', 'mailman', 'mailer', and

   196     'letterbox', start with a regexp that matches 'mail'. Expressed

   197     fully, the regexp is \bold{m{1,1}a{1,1}i{1,1}l{1,1}}, but because

   198     a character expression is automatically quantified by

   199     \bold{{1,1}}, we can simplify the regexp to \bold{mail}, i.e., an

   200     'm' followed by an 'a' followed by an 'i' followed by an 'l'. Now

   201     we can use the vertical bar \bold{|}, which means \bold{or}, to

   202     include the other two words, so our regexp for matching any of the

   203     three words becomes \bold{mail|letter|correspondence}. Match

   204     'mail' \bold{or} 'letter' \bold{or} 'correspondence'. While this

   205     regexp will match one of the three words we want to match, it will

   206     also match words we don't want to match, e.g., 'email'.  To

   207     prevent the regexp from matching unwanted words, we must tell it

   208     to begin and end the match at word boundaries. First we enclose

   209     our regexp in parentheses, \bold{(mail|letter|correspondence)}.

   210     Parentheses group expressions together, and they identify a part

   211     of the regexp that we wish to \l{capturing text}{capture}.

   212     Enclosing the expression in parentheses allows us to use it as a

   213     component in more complex regexps. It also allows us to examine

   214     which of the three words was actually matched. To force the match

   215     to begin and end on word boundaries, we enclose the regexp in

   216     \bold{\\b} \e{word boundary} assertions:

   217     \bold{\\b(mail|letter|correspondence)\\b}.  Now the regexp means:

   218     \e{Match a word boundary, followed by the regexp in parentheses,

   219     followed by a word boundary}. The \bold{\\b} assertion matches a

   220     \e position in the regexp, not a \e character. A word boundary is

   221     any non-word character, e.g., a space, newline, or the beginning

   222     or ending of a string.

   223 

   224     If we want to replace ampersand characters with the HTML entity

   225     \bold{\&}, the regexp to match is simply \bold{\&}. But this

   226     regexp will also match ampersands that have already been converted

   227     to HTML entities. We want to replace only ampersands that are not

   228     already followed by \bold{amp;}. For this, we need the negative

   229     lookahead assertion, \bold{(?!}__\bold{)}. The regexp can then be

   230     written as \bold{\&(?!amp;)}, i.e. \e{Match an ampersand that is}

   231     \bold{not} \e{followed by} \bold{amp;}.

   232 

   233     If we want to count all the occurrences of 'Eric' and 'Eirik' in a

   234     string, two valid solutions are \bold{\\b(Eric|Eirik)\\b} and

   235     \bold{\\bEi?ri[ck]\\b}. The word boundary assertion '\\b' is

   236     required to avoid matching words that contain either name,

   237     e.g. 'Ericsson'. Note that the second regexp matches more

   238     spellings than we want: 'Eric', 'Erik', 'Eiric' and 'Eirik'.

   239 

   240     Some of the examples discussed above are implemented in the

   241     \link #code-examples code examples \endlink section.

   242 

   243     \target characters-and-abbreviations-for-sets-of-characters

   244     \section1 Characters and Abbreviations for Sets of Characters

   245 

   246     \table

   247     \header \i Element \i Meaning

   248     \row \i \bold{c}

   249          \i A character represents itself unless it has a special

   250          regexp meaning. e.g. \bold{c} matches the character \e c.

   251     \row \i \bold{\\c}

   252          \i A character that follows a backslash matches the character

   253          itself, except as specified below. e.g., To match a literal

   254          caret at the beginning of a string, write \bold{\\^}.

   255     \row \i \bold{\\a}

   256          \i Matches the ASCII bell (BEL, 0x07).

   257     \row \i \bold{\\f}

   258          \i Matches the ASCII form feed (FF, 0x0C).

   259     \row \i \bold{\\n}

   260          \i Matches the ASCII line feed (LF, 0x0A, Unix newline).

   261     \row \i \bold{\\r}

   262          \i Matches the ASCII carriage return (CR, 0x0D).

   263     \row \i \bold{\\t}

   264          \i Matches the ASCII horizontal tab (HT, 0x09).

   265     \row \i \bold{\\v}

   266          \i Matches the ASCII vertical tab (VT, 0x0B).

   267     \row \i \bold{\\x\e{hhhh}}

   268          \i Matches the Unicode character corresponding to the

   269          hexadecimal number \e{hhhh} (between 0x0000 and 0xFFFF).

   270     \row \i \bold{\\0\e{ooo}} (i.e., \\zero \e{ooo})

   271          \i matches the ASCII/Latin1 character for the octal number

   272          \e{ooo} (between 0 and 0377).

   273     \row \i \bold{. (dot)}

   274          \i Matches any character (including newline).

   275     \row \i \bold{\\d}

   276          \i Matches a digit (QChar::isDigit()).

   277     \row \i \bold{\\D}

   278          \i Matches a non-digit.

   279     \row \i \bold{\\s}

   280          \i Matches a whitespace character (QChar::isSpace()).

   281     \row \i \bold{\\S}

   282          \i Matches a non-whitespace character.

   283     \row \i \bold{\\w}

   284          \i Matches a word character (QChar::isLetterOrNumber(), QChar::isMark(), or '_').

   285     \row \i \bold{\\W}

   286          \i Matches a non-word character.

   287     \row \i \bold{\\\e{n}}

   288          \i The \e{n}-th \l backreference, e.g. \\1, \\2, etc.

   289     \endtable

   290 

   291     \bold{Note:} The C++ compiler transforms backslashes in strings.

   292     To include a \bold{\\} in a regexp, enter it twice, i.e. \c{\\}.

   293     To match the backslash character itself, enter it four times, i.e.

   294     \c{\\\\}.

   295 

   296     \target sets-of-characters

   297     \section1 Sets of Characters

   298 

   299     Square brackets mean match any character contained in the square

   300     brackets. The character set abbreviations described above can

   301     appear in a character set in square brackets. Except for the

   302     character set abbreviations and the following two exceptions, 

   303     characters do not have special meanings in square brackets.

   304 

   305     \table

   306     \row \i \bold{^}

   307 

   308          \i The caret negates the character set if it occurs as the

   309          first character (i.e. immediately after the opening square

   310          bracket). \bold{[abc]} matches 'a' or 'b' or 'c', but

   311          \bold{[^abc]} matches anything \e but 'a' or 'b' or 'c'.

   312 

   313     \row \i \bold{-}

   314 

   315          \i The dash indicates a range of characters. \bold{[W-Z]}

   316          matches 'W' or 'X' or 'Y' or 'Z'.

   317 

   318     \endtable

   319 

   320     Using the predefined character set abbreviations is more portable

   321     than using character ranges across platforms and languages. For

   322     example, \bold{[0-9]} matches a digit in Western alphabets but

   323     \bold{\\d} matches a digit in \e any alphabet.

   324 

   325     Note: In other regexp documentation, sets of characters are often

   326     called "character classes".

   327 

   328     \target quantifiers

   329     \section1 Quantifiers

   330 

   331     By default, an expression is automatically quantified by

   332     \bold{{1,1}}, i.e. it should occur exactly once. In the following

   333     list, \bold{\e {E}} stands for expression. An expression is a

   334     character, or an abbreviation for a set of characters, or a set of

   335     characters in square brackets, or an expression in parentheses.

   336 

   337     \table

   338     \row \i \bold{\e {E}?}

   339 

   340          \i Matches zero or one occurrences of \e E. This quantifier

   341          means \e{The previous expression is optional}, because it

   342          will match whether or not the expression is found. \bold{\e

   343          {E}?} is the same as \bold{\e {E}{0,1}}. e.g., \bold{dents?}

   344          matches 'dent' or 'dents'.

   345 

   346     \row \i \bold{\e {E}+}

   347 

   348          \i Matches one or more occurrences of \e E. \bold{\e {E}+} is

   349          the same as \bold{\e {E}{1,}}. e.g., \bold{0+} matches '0',

   350          '00', '000', etc.

   351 

   352     \row \i \bold{\e {E}*}

   353 

   354          \i Matches zero or more occurrences of \e E. It is the same

   355          as \bold{\e {E}{0,}}. The \bold{*} quantifier is often used

   356          in error where \bold{+} should be used. For example, if

   357          \bold{\\s*$} is used in an expression to match strings that

   358          end in whitespace, it will match every string because

   359          \bold{\\s*$} means \e{Match zero or more whitespaces followed

   360          by end of string}. The correct regexp to match strings that

   361          have at least one trailing whitespace character is

   362          \bold{\\s+$}.

   363 

   364     \row \i \bold{\e {E}{n}}

   365 

   366          \i Matches exactly \e n occurrences of \e E. \bold{\e {E}{n}}

   367          is the same as repeating \e E \e n times. For example,

   368          \bold{x{5}} is the same as \bold{xxxxx}. It is also the same

   369          as \bold{\e {E}{n,n}}, e.g. \bold{x{5,5}}.

   370 

   371     \row \i \bold{\e {E}{n,}}

   372          \i Matches at least \e n occurrences of \e E.

   373 

   374     \row \i \bold{\e {E}{,m}}

   375          \i Matches at most \e m occurrences of \e E. \bold{\e {E}{,m}}

   376          is the same as \bold{\e {E}{0,m}}.

   377 

   378     \row \i \bold{\e {E}{n,m}}

   379          \i Matches at least \e n and at most \e m occurrences of \e E.

   380     \endtable

   381 

   382     To apply a quantifier to more than just the preceding character,

   383     use parentheses to group characters together in an expression. For

   384     example, \bold{tag+} matches a 't' followed by an 'a' followed by

   385     at least one 'g', whereas \bold{(tag)+} matches at least one

   386     occurrence of 'tag'.

   387 

   388     Note: Quantifiers are normally "greedy". They always match as much

   389     text as they can. For example, \bold{0+} matches the first zero it

   390     finds and all the consecutive zeros after the first zero. Applied

   391     to '20005', it matches'2\underline{000}5'. Quantifiers can be made

   392     non-greedy, see setMinimal().

   393 

   394     \target capturing parentheses

   395     \target backreferences

   396     \section1 Capturing Text

   397 

   398     Parentheses allow us to group elements together so that we can

   399     quantify and capture them. For example if we have the expression

   400     \bold{mail|letter|correspondence} that matches a string we know

   401     that \e one of the words matched but not which one. Using

   402     parentheses allows us to "capture" whatever is matched within

   403     their bounds, so if we used \bold{(mail|letter|correspondence)}

   404     and matched this regexp against the string "I sent you some email"

   405     we can use the cap() or capturedTexts() functions to extract the

   406     matched characters, in this case 'mail'.

   407 

   408     We can use captured text within the regexp itself. To refer to the

   409     captured text we use \e backreferences which are indexed from 1,

   410     the same as for cap(). For example we could search for duplicate

   411     words in a string using \bold{\\b(\\w+)\\W+\\1\\b} which means match a

   412     word boundary followed by one or more word characters followed by

   413     one or more non-word characters followed by the same text as the

   414     first parenthesized expression followed by a word boundary.

   415 

   416     If we want to use parentheses purely for grouping and not for

   417     capturing we can use the non-capturing syntax, e.g.

   418     \bold{(?:green|blue)}. Non-capturing parentheses begin '(?:' and

   419     end ')'. In this example we match either 'green' or 'blue' but we

   420     do not capture the match so we only know whether or not we matched

   421     but not which color we actually found. Using non-capturing

   422     parentheses is more efficient than using capturing parentheses

   423     since the regexp engine has to do less book-keeping.

   424 

   425     Both capturing and non-capturing parentheses may be nested.

   426 

   427     \target greedy quantifiers

   428 

   429     For historical reasons, quantifiers (e.g. \bold{*}) that apply to

   430     capturing parentheses are more "greedy" than other quantifiers.

   431     For example, \bold{a*(a)*} will match "aaa" with cap(1) == "aaa".

   432     This behavior is different from what other regexp engines do

   433     (notably, Perl). To obtain a more intuitive capturing behavior,

   434     specify QRegExp::RegExp2 to the QRegExp constructor or call

   435     setPatternSyntax(QRegExp::RegExp2).

   436 

   437     \target cap_in_a_loop

   438 

   439     When the number of matches cannot be determined in advance, a

   440     common idiom is to use cap() in a loop. For example:

   441 

   442     \snippet doc/src/snippets/code/src_corelib_tools_qregexp.cpp 0

   443 

   444     \target assertions

   445     \section1 Assertions

   446 

   447     Assertions make some statement about the text at the point where

   448     they occur in the regexp but they do not match any characters. In

   449     the following list \bold{\e {E}} stands for any expression.

   450 

   451     \table

   452     \row \i \bold{^}

   453          \i The caret signifies the beginning of the string. If you

   454          wish to match a literal \c{^} you must escape it by

   455          writing \c{\\^}. For example, \bold{^#include} will only

   456          match strings which \e begin with the characters '#include'.

   457          (When the caret is the first character of a character set it

   458          has a special meaning, see \link #sets-of-characters Sets of

   459          Characters \endlink.)

   460 

   461     \row \i \bold{$}

   462          \i The dollar signifies the end of the string. For example

   463          \bold{\\d\\s*$} will match strings which end with a digit

   464          optionally followed by whitespace. If you wish to match a

   465          literal \c{$} you must escape it by writing

   466          \c{\\$}.

   467 

   468     \row \i \bold{\\b}

   469          \i A word boundary. For example the regexp

   470          \bold{\\bOK\\b} means match immediately after a word

   471          boundary (e.g. start of string or whitespace) the letter 'O'

   472          then the letter 'K' immediately before another word boundary

   473          (e.g. end of string or whitespace). But note that the

   474          assertion does not actually match any whitespace so if we

   475          write \bold{(\\bOK\\b)} and we have a match it will only

   476          contain 'OK' even if the string is "It's \underline{OK} now".

   477 

   478     \row \i \bold{\\B}

   479          \i A non-word boundary. This assertion is true wherever

   480          \bold{\\b} is false. For example if we searched for

   481          \bold{\\Bon\\B} in "Left on" the match would fail (space

   482          and end of string aren't non-word boundaries), but it would

   483          match in "t\underline{on}ne".

   484 

   485     \row \i \bold{(?=\e E)}

   486          \i Positive lookahead. This assertion is true if the

   487          expression matches at this point in the regexp. For example,

   488          \bold{const(?=\\s+char)} matches 'const' whenever it is

   489          followed by 'char', as in 'static \underline{const} char *'.

   490          (Compare with \bold{const\\s+char}, which matches 'static

   491          \underline{const char} *'.)

   492 

   493     \row \i \bold{(?!\e E)}

   494          \i Negative lookahead. This assertion is true if the

   495          expression does not match at this point in the regexp. For

   496          example, \bold{const(?!\\s+char)} matches 'const' \e except

   497          when it is followed by 'char'.

   498     \endtable

   499 

   500     \keyword QRegExp wildcard matching

   501     \section1 Wildcard Matching

   502 

   503     Most command shells such as \e bash or \e cmd.exe support "file

   504     globbing", the ability to identify a group of files by using

   505     wildcards. The setPatternSyntax() function is used to switch

   506     between regexp and wildcard mode. Wildcard matching is much

   507     simpler than full regexps and has only four features:

   508 

   509     \table

   510     \row \i \bold{c}

   511          \i Any character represents itself apart from those mentioned

   512          below. Thus \bold{c} matches the character \e c.

   513     \row \i \bold{?}

   514          \i Matches any single character. It is the same as

   515          \bold{.} in full regexps.

   516     \row \i \bold{*}

   517          \i Matches zero or more of any characters. It is the

   518          same as \bold{.*} in full regexps.

   519     \row \i \bold{[...]}

   520          \i Sets of characters can be represented in square brackets,

   521          similar to full regexps. Within the character class, like

   522          outside, backslash has no special meaning.

   523     \endtable

   524 

   525     In the mode Wildcard, the wildcard characters cannot be

   526     escaped. In the mode WildcardUnix, the character '\' escapes the

   527     wildcard.

   528 

   529     For example if we are in wildcard mode and have strings which

   530     contain filenames we could identify HTML files with \bold{*.html}.

   531     This will match zero or more characters followed by a dot followed

   532     by 'h', 't', 'm' and 'l'.

   533 

   534     To test a string against a wildcard expression, use exactMatch().

   535     For example:

   536 

   537     \snippet doc/src/snippets/code/src_corelib_tools_qregexp.cpp 1

   538 

   539     \target perl-users

   540     \section1 Notes for Perl Users

   541 

   542     Most of the character class abbreviations supported by Perl are

   543     supported by QRegExp, see \link

   544     #characters-and-abbreviations-for-sets-of-characters characters

   545     and abbreviations for sets of characters \endlink.

   546 

   547     In QRegExp, apart from within character classes, \c{^} always

   548     signifies the start of the string, so carets must always be

   549     escaped unless used for that purpose. In Perl the meaning of caret

   550     varies automagically depending on where it occurs so escaping it

   551     is rarely necessary. The same applies to \c{$} which in

   552     QRegExp always signifies the end of the string.

   553 

   554     QRegExp's quantifiers are the same as Perl's greedy quantifiers

   555     (but see the \l{greedy quantifiers}{note above}). Non-greedy

   556     matching cannot be applied to individual quantifiers, but can be

   557     applied to all the quantifiers in the pattern. For example, to

   558     match the Perl regexp \bold{ro+?m} requires:

   559 

   560     \snippet doc/src/snippets/code/src_corelib_tools_qregexp.cpp 2

   561 

   562     The equivalent of Perl's \c{/i} option is

   563     setCaseSensitivity(Qt::CaseInsensitive).

   564 

   565     Perl's \c{/g} option can be emulated using a \l{#cap_in_a_loop}{loop}.

   566 

   567     In QRegExp \bold{.} matches any character, therefore all QRegExp

   568     regexps have the equivalent of Perl's \c{/s} option. QRegExp

   569     does not have an equivalent to Perl's \c{/m} option, but this

   570     can be emulated in various ways for example by splitting the input

   571     into lines or by looping with a regexp that searches for newlines.

   572 

   573     Because QRegExp is string oriented, there are no \\A, \\Z, or \\z

   574     assertions. The \\G assertion is not supported but can be emulated

   575     in a loop.

   576 

   577     Perl's $& is cap(0) or capturedTexts()[0]. There are no QRegExp

   578     equivalents for $`, $' or $+. Perl's capturing variables, $1, $2,

   579     ... correspond to cap(1) or capturedTexts()[1], cap(2) or

   580     capturedTexts()[2], etc.

   581 

   582     To substitute a pattern use QString::replace().

   583 

   584     Perl's extended \c{/x} syntax is not supported, nor are

   585     directives, e.g. (?i), or regexp comments, e.g. (?#comment). On

   586     the other hand, C++'s rules for literal strings can be used to

   587     achieve the same:

   588 

   589     \snippet doc/src/snippets/code/src_corelib_tools_qregexp.cpp 3

   590 

   591     Both zero-width positive and zero-width negative lookahead

   592     assertions (?=pattern) and (?!pattern) are supported with the same

   593     syntax as Perl. Perl's lookbehind assertions, "independent"

   594     subexpressions and conditional expressions are not supported.

   595 

   596     Non-capturing parentheses are also supported, with the same

   597     (?:pattern) syntax.

   598 

   599     See QString::split() and QStringList::join() for equivalents

   600     to Perl's split and join functions.

   601 

   602     Note: because C++ transforms \\'s they must be written \e twice in

   603     code, e.g. \bold{\\b} must be written \bold{\\\\b}.

   604 

   605     \target code-examples

   606     \section1 Code Examples

   607 

   608     \snippet doc/src/snippets/code/src_corelib_tools_qregexp.cpp 4

   609 

   610     The third string matches '\underline{6}'. This is a simple validation

   611     regexp for integers in the range 0 to 99.

   612 

   613     \snippet doc/src/snippets/code/src_corelib_tools_qregexp.cpp 5

   614 

   615     The second string matches '\underline{This_is-OK}'. We've used the

   616     character set abbreviation '\\S' (non-whitespace) and the anchors

   617     to match strings which contain no whitespace.

   618 

   619     In the following example we match strings containing 'mail' or

   620     'letter' or 'correspondence' but only match whole words i.e. not

   621     'email'

   622 

   623     \snippet doc/src/snippets/code/src_corelib_tools_qregexp.cpp 6

   624 

   625     The second string matches "Please write the \underline{letter}". The

   626     word 'letter' is also captured (because of the parentheses). We

   627     can see what text we've captured like this:

   628 

   629     \snippet doc/src/snippets/code/src_corelib_tools_qregexp.cpp 7

   630 

   631     This will capture the text from the first set of capturing

   632     parentheses (counting capturing left parentheses from left to

   633     right). The parentheses are counted from 1 since cap(0) is the

   634     whole matched regexp (equivalent to '&' in most regexp engines).

   635 

   636     \snippet doc/src/snippets/code/src_corelib_tools_qregexp.cpp 8

   637 

   638     Here we've passed the QRegExp to QString's replace() function to

   639     replace the matched text with new text.

   640 

   641     \snippet doc/src/snippets/code/src_corelib_tools_qregexp.cpp 9

   642 

   643     We've used the indexIn() function to repeatedly match the regexp in

   644     the string. Note that instead of moving forward by one character

   645     at a time \c pos++ we could have written \c {pos +=

   646     rx.matchedLength()} to skip over the already matched string. The

   647     count will equal 3, matching 'One \underline{Eric} another

   648     \underline{Eirik}, and an Ericsson. How many Eiriks, \underline{Eric}?'; it

   649     doesn't match 'Ericsson' or 'Eiriks' because they are not bounded

   650     by non-word boundaries.

   651 

   652     One common use of regexps is to split lines of delimited data into

   653     their component fields.

   654 

   655     \snippet doc/src/snippets/code/src_corelib_tools_qregexp.cpp 10

   656 

   657     In this example our input lines have the format company name, web

   658     address and country. Unfortunately the regexp is rather long and

   659     not very versatile -- the code will break if we add any more

   660     fields. A simpler and better solution is to look for the

   661     separator, '\\t' in this case, and take the surrounding text. The

   662     QString::split() function can take a separator string or regexp

   663     as an argument and split a string accordingly.

   664 

   665     \snippet doc/src/snippets/code/src_corelib_tools_qregexp.cpp 11

   666 

   667     Here field[0] is the company, field[1] the web address and so on.

   668 

   669     To imitate the matching of a shell we can use wildcard mode.

   670 

   671     \snippet doc/src/snippets/code/src_corelib_tools_qregexp.cpp 12

   672 

   673     Wildcard matching can be convenient because of its simplicity, but

   674     any wildcard regexp can be defined using full regexps, e.g.

   675     \bold{.*\.html$}. Notice that we can't match both \c .html and \c

   676     .htm files with a wildcard unless we use \bold{*.htm*} which will

   677     also match 'test.html.bak'. A full regexp gives us the precision

   678     we need, \bold{.*\\.html?$}.

   679 

   680     QRegExp can match case insensitively using setCaseSensitivity(),

   681     and can use non-greedy matching, see setMinimal(). By

   682     default QRegExp uses full regexps but this can be changed with

   683     setWildcard(). Searching can be forward with indexIn() or backward

   684     with lastIndexIn(). Captured text can be accessed using

   685     capturedTexts() which returns a string list of all captured

   686     strings, or using cap() which returns the captured string for the

   687     given index. The pos() function takes a match index and returns

   688     the position in the string where the match was made (or -1 if

   689     there was no match).

   690 

   691     \sa QString, QStringList, QRegExpValidator, QSortFilterProxyModel,

   692         {tools/regexp}{Regular Expression Example}

   693 */

   694 

   695 #if defined(Q_OS_VXWORKS) && defined(EOS)

   696 #  undef EOS

   697 #endif

   698 

   699 const int NumBadChars = 64;

   700 #define BadChar(ch) ((ch).unicode() % NumBadChars)

   701 

   702 const int NoOccurrence = INT_MAX;

   703 const int EmptyCapture = INT_MAX;

   704 const int InftyLen = INT_MAX;

   705 const int InftyRep = 1025;

   706 const int EOS = -1;

   707 

   708 static bool isWord(QChar ch)

   709 {

   710     return ch.isLetterOrNumber() || ch.isMark() || ch == QLatin1Char('_');

   711 }

   712 

   713 /*

   714   Merges two vectors of ints and puts the result into the first

   715   one.

   716 */

   717 static void mergeInto(QVector<int> *a, const QVector<int> &b)

   718 {

   719     int asize = a->size();

   720     int bsize = b.size();

   721     if (asize == 0) {

   722         *a = b;

   723 #ifndef QT_NO_REGEXP_OPTIM

   724     } else if (bsize == 1 && a->at(asize - 1) < b.at(0)) {

   725         a->resize(asize + 1);

   726         (*a)[asize] = b.at(0);

   727 #endif

   728     } else if (bsize >= 1) {

   729         int csize = asize + bsize;

   730         QVector<int> c(csize);

   731         int i = 0, j = 0, k = 0;

   732         while (i < asize) {

   733             if (j < bsize) {

   734                 if (a->at(i) == b.at(j)) {

   735                     ++i;

   736                     --csize;

   737                 } else if (a->at(i) < b.at(j)) {

   738                     c[k++] = a->at(i++);

   739                 } else {

   740                     c[k++] = b.at(j++);

   741                 }

   742             } else {

   743                 memcpy(c.data() + k, a->constData() + i, (asize - i) * sizeof(int));

   744                 break;

   745             }

   746         }

   747         c.resize(csize);

   748         if (j < bsize)

   749             memcpy(c.data() + k, b.constData() + j, (bsize - j) * sizeof(int));

   750         *a = c;

   751     }

   752 }

   753 

   754 #ifndef QT_NO_REGEXP_WILDCARD

   755 /*

   756   Translates a wildcard pattern to an equivalent regular expression

   757   pattern (e.g., *.cpp to .*\.cpp).

   758 

   759   If enableEscaping is true, it is possible to escape the wildcard

   760   characters with \

   761 */

   762 static QString wc2rx(const QString &wc_str, const bool enableEscaping)

   763 {

   764     const int wclen = wc_str.length();

   765     QString rx;

   766     int i = 0;

   767     bool isEscaping = false; // the previous character is '\'

   768     const QChar *wc = wc_str.unicode();

   769 

   770     while (i < wclen) {

   771         const QChar c = wc[i++];

   772         switch (c.unicode()) {

   773         case '\\':

   774             if (enableEscaping) {

   775                 if (isEscaping) {

   776                     rx += QLatin1String("\\\\");

   777                 } // we insert the \\ later if necessary

   778                 if (i+1 == wclen) { // the end

   779                     rx += QLatin1String("\\\\");

   780                 }

   781             } else {

   782                 rx += QLatin1String("\\\\");

   783             }

   784             isEscaping = true;

   785             break;

   786         case '*':

   787             if (isEscaping) {

   788                 rx += QLatin1String("\\*");

   789                 isEscaping = false;

   790             } else {

   791                 rx += QLatin1String(".*");

   792             }

   793             break;

   794         case '?':

   795             if (isEscaping) {

   796                 rx += QLatin1String("\\?");

   797                 isEscaping = false;

   798             } else {

   799                 rx += QLatin1Char('.');

   800             }

   801 

   802             break;

   803         case '$':

   804         case '(':

   805         case ')':

   806         case '+':

   807         case '.':

   808         case '^':

   809         case '{':

   810         case '|':

   811         case '}':

   812             if (isEscaping) {

   813                 isEscaping = false;

   814                 rx += QLatin1String("\\\\");

   815             }

   816             rx += QLatin1Char('\\');

   817             rx += c;

   818             break;

   819          case '[':

   820             if (isEscaping) {

   821                 isEscaping = false;

   822                 rx += QLatin1String("\\[");

   823             } else {

   824                 rx += c;

   825                 if (wc[i] == QLatin1Char('^'))

   826                     rx += wc[i++];

   827                 if (i < wclen) {

   828                     if (rx[i] == QLatin1Char(']'))

   829                         rx += wc[i++];

   830                     while (i < wclen && wc[i] != QLatin1Char(']')) {

   831                         if (wc[i] == QLatin1Char('\\'))

   832                             rx += QLatin1Char('\\');

   833                         rx += wc[i++];

   834                     }

   835                 }

   836             }

   837              break;

   838 

   839         case ']':

   840             if(isEscaping){

   841                 isEscaping = false;

   842                 rx += QLatin1String("\\");

   843             }

   844             rx += c;

   845             break;

   846 

   847         default:

   848             if(isEscaping){

   849                 isEscaping = false;

   850                 rx += QLatin1String("\\\\");

   851             }

   852             rx += c;

   853         }

   854     }

   855     return rx;

   856 }

   857 #endif

   858 

   859 static int caretIndex(int offset, QRegExp::CaretMode caretMode)

   860 {

   861     if (caretMode == QRegExp::CaretAtZero) {

   862         return 0;

   863     } else if (caretMode == QRegExp::CaretAtOffset) {

   864         return offset;

   865     } else { // QRegExp::CaretWontMatch

   866         return -1;

   867     }

   868 }

   869 

   870 /*

   871     The QRegExpEngineKey struct uniquely identifies an engine.

   872 */

   873 struct QRegExpEngineKey

   874 {

   875     QString pattern;

   876     QRegExp::PatternSyntax patternSyntax;

   877     Qt::CaseSensitivity cs;

   878 

   879     inline QRegExpEngineKey(const QString &pattern, QRegExp::PatternSyntax patternSyntax,

   880                             Qt::CaseSensitivity cs)

   881         : pattern(pattern), patternSyntax(patternSyntax), cs(cs) {}

   882 

   883     inline void clear() {

   884         pattern.clear();

   885         patternSyntax = QRegExp::RegExp;

   886         cs = Qt::CaseSensitive;

   887     }

   888 };

   889 

   890 Q_STATIC_GLOBAL_OPERATOR bool operator==(const QRegExpEngineKey &key1, const QRegExpEngineKey &key2)

   891 {

   892     return key1.pattern == key2.pattern && key1.patternSyntax == key2.patternSyntax

   893            && key1.cs == key2.cs;

   894 }

   895 

   896 class QRegExpEngine;

   897 

   898 //Q_DECLARE_TYPEINFO(QVector<int>, Q_MOVABLE_TYPE);

   899 

   900 /*

   901   This is the engine state during matching.

   902 */

   903 struct QRegExpMatchState

   904 {

   905     const QChar *in; // a pointer to the input string data

   906     int pos; // the current position in the string

   907     int caretPos;

   908     int len; // the length of the input string

   909     bool minimal; // minimal matching?

   910     int *bigArray; // big array holding the data for the next pointers

   911     int *inNextStack; // is state is nextStack?

   912     int *curStack; // stack of current states

   913     int *nextStack; // stack of next states

   914     int *curCapBegin; // start of current states' captures

   915     int *nextCapBegin; // start of next states' captures

   916     int *curCapEnd; // end of current states' captures

   917     int *nextCapEnd; // end of next states' captures

   918     int *tempCapBegin; // start of temporary captures

   919     int *tempCapEnd; // end of temporary captures

   920     int *capBegin; // start of captures for a next state

   921     int *capEnd; // end of captures for a next state

   922     int *slideTab; // bump-along slide table for bad-character heuristic

   923     int *captured; // what match() returned last

   924     int slideTabSize; // size of slide table

   925     int capturedSize;

   926 #ifndef QT_NO_REGEXP_BACKREF

   927     QList<QVector<int> > sleeping; // list of back-reference sleepers

   928 #endif

   929     int matchLen; // length of match

   930     int oneTestMatchedLen; // length of partial match

   931 

   932     const QRegExpEngine *eng;

   933 

   934     inline QRegExpMatchState() : bigArray(0), captured(0) {}

   935     inline ~QRegExpMatchState() { free(bigArray); }

   936 

   937     void drain() { free(bigArray); bigArray = 0; captured = 0; } // to save memory

   938     void prepareForMatch(QRegExpEngine *eng);

   939     void match(const QChar *str, int len, int pos, bool minimal,

   940         bool oneTest, int caretIndex);

   941     bool matchHere();

   942     bool testAnchor(int i, int a, const int *capBegin);

   943 };

   944 

   945 /*

   946   The struct QRegExpAutomatonState represents one state in a modified NFA. The

   947   input characters matched are stored in the state instead of on

   948   the transitions, something possible for an automaton

   949   constructed from a regular expression.

   950 */

   951 struct QRegExpAutomatonState

   952 {

   953 #ifndef QT_NO_REGEXP_CAPTURE

   954     int atom; // which atom does this state belong to?

   955 #endif

   956     int match; // what does it match? (see CharClassBit and BackRefBit)

   957     QVector<int> outs; // out-transitions

   958     QMap<int, int> reenter; // atoms reentered when transiting out

   959     QMap<int, int> anchors; // anchors met when transiting out

   960 

   961     inline QRegExpAutomatonState() { }

   962 #ifndef QT_NO_REGEXP_CAPTURE

   963     inline QRegExpAutomatonState(int a, int m)

   964         : atom(a), match(m) { }

   965 #else

   966     inline QRegExpAutomatonState(int m)

   967         : match(m) { }

   968 #endif

   969 };

   970 

   971 Q_DECLARE_TYPEINFO(QRegExpAutomatonState, Q_MOVABLE_TYPE);

   972 

   973 /*

   974   The struct QRegExpCharClassRange represents a range of characters (e.g.,

   975   [0-9] denotes range 48 to 57).

   976 */

   977 struct QRegExpCharClassRange

   978 {

   979     ushort from; // 48

   980     ushort len; // 10

   981 };

   982 

   983 Q_DECLARE_TYPEINFO(QRegExpCharClassRange, Q_PRIMITIVE_TYPE);

   984 

   985 #ifndef QT_NO_REGEXP_CAPTURE

   986 /*

   987   The struct QRegExpAtom represents one node in the hierarchy of regular

   988   expression atoms.

   989 */

   990 struct QRegExpAtom

   991 {

   992     enum { NoCapture = -1, OfficialCapture = -2, UnofficialCapture = -3 };

   993 

   994     int parent; // index of parent in array of atoms

   995     int capture; // index of capture, from 1 to ncap - 1

   996 };

   997 

   998 Q_DECLARE_TYPEINFO(QRegExpAtom, Q_PRIMITIVE_TYPE);

   999 #endif

  1000 

  1001 struct QRegExpLookahead;

  1002 

  1003 #ifndef QT_NO_REGEXP_ANCHOR_ALT

  1004 /*

  1005   The struct QRegExpAnchorAlternation represents a pair of anchors with

  1006   OR semantics.

  1007 */

  1008 struct QRegExpAnchorAlternation

  1009 {

  1010     int a; // this anchor...

  1011     int b; // ...or this one

  1012 };

  1013 

  1014 Q_DECLARE_TYPEINFO(QRegExpAnchorAlternation, Q_PRIMITIVE_TYPE);

  1015 #endif

  1016 

  1017 #ifndef QT_NO_REGEXP_CCLASS

  1018 /*

  1019   The class QRegExpCharClass represents a set of characters, such as can

  1020   be found in regular expressions (e.g., [a-z] denotes the set

  1021   {a, b, ..., z}).

  1022 */

  1023 class QRegExpCharClass

  1024 {

  1025 public:

  1026     QRegExpCharClass();

  1027     inline QRegExpCharClass(const QRegExpCharClass &cc) { operator=(cc); }

  1028 

  1029     QRegExpCharClass &operator=(const QRegExpCharClass &cc);

  1030 

  1031     void clear();

  1032     bool negative() const { return n; }

  1033     void setNegative(bool negative);

  1034     void addCategories(int cats);

  1035     void addRange(ushort from, ushort to);

  1036     void addSingleton(ushort ch) { addRange(ch, ch); }

  1037 

  1038     bool in(QChar ch) const;

  1039 #ifndef QT_NO_REGEXP_OPTIM

  1040     const QVector<int> &firstOccurrence() const { return occ1; }

  1041 #endif

  1042 

  1043 #if defined(QT_DEBUG)

  1044     void dump() const;

  1045 #endif

  1046 

  1047 private:

  1048     int c; // character classes

  1049     QVector<QRegExpCharClassRange> r; // character ranges

  1050     bool n; // negative?

  1051 #ifndef QT_NO_REGEXP_OPTIM

  1052     QVector<int> occ1; // first-occurrence array

  1053 #endif

  1054 };

  1055 #else

  1056 struct QRegExpCharClass

  1057 {

  1058     int dummy;

  1059 

  1060 #ifndef QT_NO_REGEXP_OPTIM

  1061     QRegExpCharClass() { occ1.fill(0, NumBadChars); }

  1062 

  1063     const QVector<int> &firstOccurrence() const { return occ1; }

  1064     QVector<int> occ1;

  1065 #endif

  1066 };

  1067 #endif

  1068 

  1069 Q_DECLARE_TYPEINFO(QRegExpCharClass, Q_MOVABLE_TYPE);

  1070 

  1071 /*

  1072   The QRegExpEngine class encapsulates a modified nondeterministic

  1073   finite automaton (NFA).

  1074 */

  1075 class QRegExpEngine

  1076 {

  1077 public:

  1078     QRegExpEngine(Qt::CaseSensitivity cs, bool greedyQuantifiers)

  1079         : cs(cs), greedyQuantifiers(greedyQuantifiers) { setup(); }

  1080 

  1081     QRegExpEngine(const QRegExpEngineKey &key);

  1082     ~QRegExpEngine();

  1083 

  1084     bool isValid() const { return valid; }

  1085     const QString &errorString() const { return yyError; }

  1086     int numCaptures() const { return officialncap; }

  1087 

  1088     int createState(QChar ch);

  1089     int createState(const QRegExpCharClass &cc);

  1090 #ifndef QT_NO_REGEXP_BACKREF

  1091     int createState(int bref);

  1092 #endif

  1093 

  1094     void addCatTransitions(const QVector<int> &from, const QVector<int> &to);

  1095 #ifndef QT_NO_REGEXP_CAPTURE

  1096     void addPlusTransitions(const QVector<int> &from, const QVector<int> &to, int atom);

  1097 #endif

  1098 

  1099 #ifndef QT_NO_REGEXP_ANCHOR_ALT

  1100     int anchorAlternation(int a, int b);

  1101     int anchorConcatenation(int a, int b);

  1102 #else

  1103     int anchorAlternation(int a, int b) { return a & b; }

  1104     int anchorConcatenation(int a, int b) { return a | b; }

  1105 #endif

  1106     void addAnchors(int from, int to, int a);

  1107 

  1108 #ifndef QT_NO_REGEXP_OPTIM

  1109     void heuristicallyChooseHeuristic();

  1110 #endif

  1111 

  1112 #if defined(QT_DEBUG)

  1113     void dump() const;

  1114 #endif

  1115 

  1116     QAtomicInt ref;

  1117 

  1118 private:

  1119     enum { CharClassBit = 0x10000, BackRefBit = 0x20000 };

  1120     enum { InitialState = 0, FinalState = 1 };

  1121 

  1122     void setup();

  1123     int setupState(int match);

  1124 

  1125     /*

  1126       Let's hope that 13 lookaheads and 14 back-references are

  1127       enough.

  1128      */

  1129     enum { MaxLookaheads = 13, MaxBackRefs = 14 };

  1130     enum { Anchor_Dollar = 0x00000001, Anchor_Caret = 0x00000002, Anchor_Word = 0x00000004,

  1131            Anchor_NonWord = 0x00000008, Anchor_FirstLookahead = 0x00000010,

  1132            Anchor_BackRef1Empty = Anchor_FirstLookahead << MaxLookaheads,

  1133            Anchor_BackRef0Empty = Anchor_BackRef1Empty >> 1,

  1134            Anchor_Alternation = unsigned(Anchor_BackRef1Empty) << MaxBackRefs,