/****************************************************************************

**

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

** All rights reserved.

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

**

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

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

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

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

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

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

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

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

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

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

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

**

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

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

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

**

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

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

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

#include "qregexp.h"

#include "qalgorithms.h"

#include "qbitarray.h"

#include "qcache.h"

#include "qdatastream.h"

#include "qlist.h"

#include "qmap.h"

#include "qmutex.h"

#include "qstring.h"

#include "qstringlist.h"

#include "qstringmatcher.h"

#include "qvector.h"

#include "private/qfunctions_p.h"

#include <limits.h>

QT_BEGIN_NAMESPACE

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

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

// error strings for the regexp parser

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

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

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

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

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

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

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

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

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

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

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

/*

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

*/

/*!

    \class QRegExp

    \reentrant

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

    \ingroup tools

    \ingroup shared

    \keyword regular expression

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

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

    \table

    \row \i Validation

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

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

    \row \i Searching

         \i A regexp provides more powerful pattern matching than

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

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

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

     \row \i Search and Replace

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

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

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

         an \e{amp;}.

    \row \i String Splitting

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

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

    \endtable

    A brief introduction to regexps is presented, a description of

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

    documentation itself. QRegExp is modeled on Perl's regexp

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

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

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

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

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

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

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

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

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

    \tableofcontents

    \section1 Introduction

    Regexps are built up from expressions, quantifiers, and

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

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

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

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

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

    captital letter in the English alphabet is written as

    \bold{[A-Z]}.

    A quantifier specifies the number of occurrences of an expression

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

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

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

    five.

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

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

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

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

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

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

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

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

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

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

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

    will not fail.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    characters but locations in the string.

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

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

    characters and some quantifiers are so common that they have been

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

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

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

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

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

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

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

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

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

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

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

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

    immediately by end of string}.

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

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

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

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

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

    a character expression is automatically quantified by

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

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

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

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

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

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

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

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

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

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

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

    Parentheses group expressions together, and they identify a part

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

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

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

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

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

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

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

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

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

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

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

    or ending of a string.

    If we want to replace ampersand characters with the HTML entity

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

    regexp will also match ampersands that have already been converted

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

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

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

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

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

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

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

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

    required to avoid matching words that contain either name,

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

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

    Some of the examples discussed above are implemented in the

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

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

    \section1 Characters and Abbreviations for Sets of Characters

    \table

    \header \i Element \i Meaning

    \row \i \bold{c}

         \i A character represents itself unless it has a special

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

    \row \i \bold{\\c}

         \i A character that follows a backslash matches the character

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

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

    \row \i \bold{\\a}

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

    \row \i \bold{\\f}

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

    \row \i \bold{\\n}

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

    \row \i \bold{\\r}

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

    \row \i \bold{\\t}

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

    \row \i \bold{\\v}

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

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

         \i Matches the Unicode character corresponding to the

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

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

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

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

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

         \i Matches any character (including newline).

    \row \i \bold{\\d}

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

    \row \i \bold{\\D}

         \i Matches a non-digit.

    \row \i \bold{\\s}

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

    \row \i \bold{\\S}

         \i Matches a non-whitespace character.

    \row \i \bold{\\w}

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

    \row \i \bold{\\W}

         \i Matches a non-word character.

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

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

    \endtable

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

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

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

    \c{\\\\}.

    \target sets-of-characters

    \section1 Sets of Characters

    Square brackets mean match any character contained in the square

    brackets. The character set abbreviations described above can

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

    character set abbreviations and the following two exceptions, 

    characters do not have special meanings in square brackets.

    \table

    \row \i \bold{^}

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

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

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

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

    \row \i \bold{-}

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

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

    \endtable

    Using the predefined character set abbreviations is more portable

    than using character ranges across platforms and languages. For

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

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

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

    called "character classes".

    \target quantifiers

    \section1 Quantifiers

    By default, an expression is automatically quantified by

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

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

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

    characters in square brackets, or an expression in parentheses.

    \table

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

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

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

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

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

         matches 'dent' or 'dents'.

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

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

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

         '00', '000', etc.

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

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

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

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

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

         end in whitespace, it will match every string because

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

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

         have at least one trailing whitespace character is

         \bold{\\s+$}.

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

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

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

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

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

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

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

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

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

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

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

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

    \endtable

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

    use parentheses to group characters together in an expression. For

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

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

    occurrence of 'tag'.

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

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

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

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

    non-greedy, see setMinimal().

    \target capturing parentheses

    \target backreferences

    \section1 Capturing Text

    Parentheses allow us to group elements together so that we can

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

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

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

    parentheses allows us to "capture" whatever is matched within

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

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

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

    matched characters, in this case 'mail'.

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

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

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

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

    word boundary followed by one or more word characters followed by

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

    first parenthesized expression followed by a word boundary.

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

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

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

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

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

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

    parentheses is more efficient than using capturing parentheses

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

    Both capturing and non-capturing parentheses may be nested.

    \target greedy quantifiers

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

    capturing parentheses are more "greedy" than other quantifiers.

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

    This behavior is different from what other regexp engines do

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

    specify QRegExp::RegExp2 to the QRegExp constructor or call

    setPatternSyntax(QRegExp::RegExp2).

    \target cap_in_a_loop

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

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

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

    \target assertions

    \section1 Assertions

    Assertions make some statement about the text at the point where

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

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

    \table

    \row \i \bold{^}

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

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

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

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

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

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

         Characters \endlink.)

    \row \i \bold{$}

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

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

         optionally followed by whitespace. If you wish to match a

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

         \c{\\$}.

    \row \i \bold{\\b}

         \i A word boundary. For example the regexp

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

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

         then the letter 'K' immediately before another word boundary

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

         assertion does not actually match any whitespace so if we

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

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

    \row \i \bold{\\B}

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

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

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

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

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

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

         \i Positive lookahead. This assertion is true if the

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

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

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

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

         \underline{const char} *'.)

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

         \i Negative lookahead. This assertion is true if the

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

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

         when it is followed by 'char'.

    \endtable

    \keyword QRegExp wildcard matching

    \section1 Wildcard Matching

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

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

    wildcards. The setPatternSyntax() function is used to switch

    between regexp and wildcard mode. Wildcard matching is much

    simpler than full regexps and has only four features:

    \table

    \row \i \bold{c}

         \i Any character represents itself apart from those mentioned

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

    \row \i \bold{?}

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

         \bold{.} in full regexps.

    \row \i \bold{*}

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

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

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

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

         similar to full regexps. Within the character class, like

         outside, backslash has no special meaning.

    \endtable

    In the mode Wildcard, the wildcard characters cannot be

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

    wildcard.