qregexp.cpp File Reference

#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>

Go to the source code of this file.

Classes
struct	QRegExpAnchorAlternation
struct	QRegExpAtom
struct	QRegExpAutomatonState
class	QRegExpCharClass
struct	QRegExpCharClassRange
class	QRegExpEngine
class	QRegExpEngine::Box
struct	QRegExpEngineKey
struct	QRegExpLookahead
struct	QRegExpMatchState
struct	QRegExpPrivate

Macros
#define	BadChar(ch)   ((ch).unicode() % NumBadChars)
#define	RXERR_CATEGORY   QT_TRANSLATE_NOOP("QRegExp", "invalid category")
#define	RXERR_CHARCLASS   QT_TRANSLATE_NOOP("QRegExp", "bad char class syntax")
#define	RXERR_DISABLED   QT_TRANSLATE_NOOP("QRegExp", "disabled feature used")
#define	RXERR_END   QT_TRANSLATE_NOOP("QRegExp", "unexpected end")
#define	RXERR_INTERVAL   QT_TRANSLATE_NOOP("QRegExp", "invalid interval")
#define	RXERR_LEFTDELIM   QT_TRANSLATE_NOOP("QRegExp", "missing left delim")
#define	RXERR_LIMIT   QT_TRANSLATE_NOOP("QRegExp", "met internal limit")
#define	RXERR_LOOKAHEAD   QT_TRANSLATE_NOOP("QRegExp", "bad lookahead syntax")
#define	RXERR_LOOKBEHIND   QT_TRANSLATE_NOOP("QRegExp", "lookbehinds not supported, see QTBUG-2371")
#define	RXERR_OCTAL   QT_TRANSLATE_NOOP("QRegExp", "invalid octal value")
#define	RXERR_OK   QT_TRANSLATE_NOOP("QRegExp", "no error occurred")
#define	RXERR_REPETITION   QT_TRANSLATE_NOOP("QRegExp", "bad repetition syntax")
#define	YYREDO()

Typedefs
typedef QCache< QRegExpEngineKey, QRegExpEngine >	EngineCache

Functions
static int	caretIndex (int offset, QRegExp::CaretMode caretMode)
static void	derefEngine (QRegExpEngine *eng, const QRegExpEngineKey &key)
static void	invalidateEngine (QRegExpPrivate *priv)
static bool	isBetterCapture (int ncap, const int *begin1, const int *end1, const int *begin2, const int *end2)
static bool	isWord (QChar ch)
static void	mergeInto (QVector< int > *a, const QVector< int > &b)
Q_STATIC_GLOBAL_OPERATOR bool	operator== (const QRegExpEngineKey &key1, const QRegExpEngineKey &key2)
static void	prepareEngine (QRegExpPrivate *priv)
static void	prepareEngine_helper (QRegExpPrivate *priv)
static void	prepareEngineForMatch (QRegExpPrivate *priv, const QString &str)
	Q_DECLARE_TYPEINFO (QRegExpAutomatonState, Q_MOVABLE_TYPE)
	Q_DECLARE_TYPEINFO (QRegExpCharClassRange, Q_PRIMITIVE_TYPE)
	Q_DECLARE_TYPEINFO (QRegExpAtom, Q_PRIMITIVE_TYPE)
	Q_DECLARE_TYPEINFO (QRegExpAnchorAlternation, Q_PRIMITIVE_TYPE)
	Q_DECLARE_TYPEINFO (QRegExpCharClass, Q_MOVABLE_TYPE)
int	qFindString (const QChar *haystack, int haystackLen, int from, const QChar *needle, int needleLen, Qt::CaseSensitivity cs)
uint	qHash (const QRegExpEngineKey &key)
Q_CORE_EXPORT QString	qt_regexp_toCanonical (const QString &pattern, QRegExp::PatternSyntax patternSyntax)
static QString	wc2rx (const QString &wc_str, const bool enableEscaping)

Variables
const int	EmptyCapture = INT_MAX
const int	EOS = -1
const int	InftyLen = INT_MAX
const int	InftyRep = 1025
const int	NoOccurrence = INT_MAX
const int	NumBadChars = 64

Macro Definition Documentation

BadChar

#define BadChar

(

ch

)

((ch).unicode() % NumBadChars)

Definition at line 699 of file qregexp.cpp.

Referenced by QRegExpEngine::badCharMatch(), QRegExpCharClass::in(), and QRegExpEngine::Box::set().

RXERR_CATEGORY

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

Definition at line 76 of file qregexp.cpp.

Referenced by QRegExpEngine::getEscape().

RXERR_CHARCLASS

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

Definition at line 67 of file qregexp.cpp.

Referenced by QRegExpEngine::getEscape(), and QRegExpEngine::getToken().

RXERR_DISABLED

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

Definition at line 66 of file qregexp.cpp.

Referenced by QRegExpEngine::getEscape(), QRegExpEngine::getToken(), and QRegExpEngine::parseAtom().

RXERR_END

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

Definition at line 73 of file qregexp.cpp.

Referenced by QRegExpEngine::getEscape(), QRegExpEngine::getToken(), and QRegExpEngine::parseAtom().

RXERR_INTERVAL

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

Definition at line 75 of file qregexp.cpp.

Referenced by QRegExpEngine::getToken().

RXERR_LEFTDELIM

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

Definition at line 72 of file qregexp.cpp.

Referenced by QRegExpEngine::getToken(), and QRegExpEngine::QRegExpEngine().

RXERR_LIMIT

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

Definition at line 74 of file qregexp.cpp.

Referenced by QRegExpEngine::addLookahead(), and QRegExpEngine::createState().

RXERR_LOOKAHEAD

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

Definition at line 68 of file qregexp.cpp.

Referenced by QRegExpEngine::getToken(), and QRegExpEngine::parseAtom().

RXERR_LOOKBEHIND

#define RXERR_LOOKBEHIND   QT_TRANSLATE_NOOP("QRegExp", "lookbehinds not supported, see QTBUG-2371")

Definition at line 69 of file qregexp.cpp.

Referenced by QRegExpEngine::getToken().

RXERR_OCTAL

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

Definition at line 71 of file qregexp.cpp.

Referenced by QRegExpEngine::getEscape().

RXERR_OK

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

Definition at line 65 of file qregexp.cpp.

Referenced by QRegExp::errorString().

RXERR_REPETITION

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

Definition at line 70 of file qregexp.cpp.

Referenced by QRegExpEngine::getRep(), QRegExpEngine::getToken(), and QRegExpEngine::parseAtom().

YYREDO

#define YYREDO

(

)

Value:

yyIn = in, yyPos0 = pos0, yyPos = pos, yyLen = len, yyCh = ch, \
        *yyCharClass = charClass, yyMinRep = 0, yyMaxRep = 0, yyTok = tok

Referenced by QRegExpEngine::parseFactor().

Typedef Documentation

EngineCache

typedef QCache<QRegExpEngineKey, QRegExpEngine> EngineCache

Definition at line 3677 of file qregexp.cpp.

Function Documentation

caretIndex()

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

static

Definition at line 858 of file qregexp.cpp.

Referenced by QRegExpMatchState::drain(), QRegExp::indexIn(), QRegExp::lastIndexIn(), and QRegExpMatchState::match().

{
    if (caretMode == QRegExp::CaretAtZero) {
        return 0;
    } else if (caretMode == QRegExp::CaretAtOffset) {
        return offset;
    } else { // QRegExp::CaretWontMatch
        return -1;
    }
}

derefEngine()

static void derefEngine ( QRegExpEngine *  eng, const QRegExpEngineKey &  key  )

static

Definition at line 3682 of file qregexp.cpp.

Referenced by invalidateEngine().

{
    if (!eng->ref.deref()) {
#if !defined(QT_NO_REGEXP_OPTIM)
        if (globalEngineCache()) {
            QMutexLocker locker(mutex());
            QT_TRY {
                globalEngineCache()->insert(key, eng, 4 + key.pattern.length() / 4);
            } QT_CATCH(const std::bad_alloc &) {
                // in case of an exception (e.g. oom), just delete the engine
                delete eng;
            }
        } else {
            delete eng;
        }
#else
        Q_UNUSED(key);
        delete eng;
#endif
    }
}

invalidateEngine()

static void invalidateEngine ( QRegExpPrivate *  priv )

static

Definition at line 3742 of file qregexp.cpp.

Referenced by QRegExp::operator=(), QRegExp::setCaseSensitivity(), QRegExp::setPattern(), QRegExp::setPatternSyntax(), and QRegExp::~QRegExp().

{
    if (priv->eng != 0) {
        derefEngine(priv->eng, priv->engineKey);
        priv->eng = 0;
        priv->matchState.drain();
    }
}

isBetterCapture()

static bool isBetterCapture ( int  ncap, const int *  begin1, const int *  end1, const int *  begin2, const int *  end2  )

static

Definition at line 1785 of file qregexp.cpp.

Referenced by QRegExpMatchState::matchHere().

{
    for (int i = 0; i < ncap; i++) {
        int delta = begin2[i] - begin1[i]; // it has to start early...
        if (delta == 0)
            delta = end1[i] - end2[i]; // ...and end late

        if (delta != 0)
            return delta > 0;
    }
    return false;
}

isWord()

static bool isWord ( QChar  ch )

static

Definition at line 707 of file qregexp.cpp.

Referenced by QRegExpMatchState::testAnchor().

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

mergeInto()

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

static

Definition at line 716 of file qregexp.cpp.

Referenced by QRegExpEngine::addCatTransitions(), QRegExpEngine::addPlusTransitions(), QRegExpEngine::Box::cat(), and QRegExpEngine::Box::orx().

{
    int asize = a->size();
    int bsize = b.size();
    if (asize == 0) {
        *a = b;
#ifndef QT_NO_REGEXP_OPTIM
    } else if (bsize == 1 && a->at(asize - 1) < b.at(0)) {
        a->resize(asize + 1);
        (*a)[asize] = b.at(0);
#endif
    } else if (bsize >= 1) {
        int csize = asize + bsize;
        QVector<int> c(csize);
        int i = 0, j = 0, k = 0;
        while (i < asize) {
            if (j < bsize) {
                if (a->at(i) == b.at(j)) {
                    ++i;
                    --csize;
                } else if (a->at(i) < b.at(j)) {
                    c[k++] = a->at(i++);
                } else {
                    c[k++] = b.at(j++);
                }
            } else {
                memcpy(c.data() + k, a->constData() + i, (asize - i) * sizeof(int));
                break;
            }
        }
        c.resize(csize);
        if (j < bsize)
            memcpy(c.data() + k, b.constData() + j, (bsize - j) * sizeof(int));
        *a = c;
    }
}

operator==()

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

Definition at line 889 of file qregexp.cpp.

{
    return key1.pattern == key2.pattern && key1.patternSyntax == key2.patternSyntax
           && key1.cs == key2.cs;
}

prepareEngine()

static void prepareEngine ( QRegExpPrivate *  priv )

inlinestatic

Definition at line 3723 of file qregexp.cpp.

Referenced by QRegExp::captureCount(), QRegExp::capturedTexts(), QRegExp::isValid(), QRegExp::operator=(), prepareEngineForMatch(), and QRegExp::QRegExp().

{
    if (priv->eng)
        return;
    prepareEngine_helper(priv);
}

prepareEngine_helper()

static void prepareEngine_helper ( QRegExpPrivate *  priv )

static

Definition at line 3704 of file qregexp.cpp.

Referenced by prepareEngine().

{
    bool initMatchState = !priv->eng;
#if !defined(QT_NO_REGEXP_OPTIM)
    if (!priv->eng && globalEngineCache()) {
        QMutexLocker locker(mutex());
        priv->eng = globalEngineCache()->take(priv->engineKey);
        if (priv->eng != 0)
            priv->eng->ref.ref();
    }
#endif // QT_NO_REGEXP_OPTIM

    if (!priv->eng)
        priv->eng = new QRegExpEngine(priv->engineKey);

    if (initMatchState)
        priv->matchState.prepareForMatch(priv->eng);
}

prepareEngineForMatch()

static void prepareEngineForMatch ( QRegExpPrivate *  priv, const QString &  str  )

static

Definition at line 3730 of file qregexp.cpp.

Referenced by QRegExp::exactMatch(), QRegExp::indexIn(), and QRegExp::lastIndexIn().

{
    prepareEngine(priv);
    priv->matchState.prepareForMatch(priv->eng);
#ifndef QT_NO_REGEXP_CAPTURE
    priv->t = str;
    priv->capturedCache.clear();
#else
    Q_UNUSED(str);
#endif
}

Q_DECLARE_TYPEINFO() [1/5]

Q_DECLARE_TYPEINFO	(	QRegExpAutomatonState	,
		Q_MOVABLE_TYPE
	)

Referenced by QRegExpAutomatonState::QRegExpAutomatonState().

Q_DECLARE_TYPEINFO() [2/5]

Q_DECLARE_TYPEINFO	(	QRegExpCharClassRange	,
		Q_PRIMITIVE_TYPE
	)

Q_DECLARE_TYPEINFO() [3/5]

Q_DECLARE_TYPEINFO	(	QRegExpAtom	,
		Q_PRIMITIVE_TYPE
	)

Q_DECLARE_TYPEINFO() [4/5]

Q_DECLARE_TYPEINFO	(	QRegExpAnchorAlternation	,
		Q_PRIMITIVE_TYPE
	)

Q_DECLARE_TYPEINFO() [5/5]

Q_DECLARE_TYPEINFO	(	QRegExpCharClass	,
		Q_MOVABLE_TYPE
	)

qFindString()

int qFindString	(	const QChar *	haystack,
		int	haystackLen,
		int	from,
		const QChar *	needle,
		int	needleLen,
		Qt::CaseSensitivity	cs
	)

Definition at line 2753 of file qstring.cpp.

Referenced by QString::indexOf(), QStringRef::indexOf(), QRegExpMatchState::match(), qt_find_latin1_string(), and qt_string_count().

{
    const int l = haystackLen;
    const int sl = needleLen;
    if (from < 0)
        from += l;
    if (uint(sl + from) > (uint)l)
        return -1;
    if (!sl)
        return from;
    if (!l)
        return -1;

    if (sl == 1)
        return findChar(haystack0, haystackLen, needle0[0], from, cs);

    /*
        We use the Boyer-Moore algorithm in cases where the overhead
        for the skip table should pay off, otherwise we use a simple
        hash function.
    */
    if (l > 500 && sl > 5)
        return qFindStringBoyerMoore(haystack0, haystackLen, from,
            needle0, needleLen, cs);

    /*
        We use some hashing for efficiency's sake. Instead of
        comparing strings, we compare the hash value of str with that
        of a part of this QString. Only if that matches, we call
        ucstrncmp() or ucstrnicmp().
    */
    const ushort *needle = (const ushort *)needle0;
    const ushort *haystack = (const ushort *)haystack0 + from;
    const ushort *end = (const ushort *)haystack0 + (l-sl);
    const int sl_minus_1 = sl-1;
    int hashNeedle = 0, hashHaystack = 0, idx;

    if (cs == Qt::CaseSensitive) {
        for (idx = 0; idx < sl; ++idx) {
            hashNeedle = ((hashNeedle<<1) + needle[idx]);
            hashHaystack = ((hashHaystack<<1) + haystack[idx]);
        }
        hashHaystack -= haystack[sl_minus_1];

        while (haystack <= end) {
            hashHaystack += haystack[sl_minus_1];
            if (hashHaystack == hashNeedle
                 && ucstrncmp((const QChar *)needle, (const QChar *)haystack, sl) == 0)
                return haystack - (const ushort *)haystack0;

            REHASH(*haystack);
            ++haystack;
        }
    } else {
        const ushort *haystack_start = (const ushort *)haystack0;
        for (idx = 0; idx < sl; ++idx) {
            hashNeedle = (hashNeedle<<1) + foldCase(needle + idx, needle);
            hashHaystack = (hashHaystack<<1) + foldCase(haystack + idx, haystack_start);
        }
        hashHaystack -= foldCase(haystack + sl_minus_1, haystack_start);

        while (haystack <= end) {
            hashHaystack += foldCase(haystack + sl_minus_1, haystack_start);
            if (hashHaystack == hashNeedle && ucstrnicmp(needle, haystack, sl) == 0)
                return haystack - (const ushort *)haystack0;

            REHASH(foldCase(haystack, haystack_start));
            ++haystack;
        }
    }
    return -1;
}

qHash()

uint qHash

(

const QRegExpEngineKey &

key

)

Definition at line 3672 of file qregexp.cpp.

{
    return qHash(key.pattern);
}

qt_regexp_toCanonical()

Q_CORE_EXPORT QString qt_regexp_toCanonical	(	const QString &	pattern,
		QRegExp::PatternSyntax	patternSyntax
	)

Warning

This function is not part of the public interface. convert the pattern string to the RegExp syntax.

This is also used by QScriptEngine::newRegExp to convert to a pattern that JavaScriptCore can understan

Definition at line 1323 of file qregexp.cpp.

Referenced by QScriptEnginePrivate::detachAllRegisteredScriptStrings(), QScriptEnginePrivate::newRegExp(), and QRegExpEngine::QRegExpEngine().

{
    switch (patternSyntax) {
#ifndef QT_NO_REGEXP_WILDCARD
    case QRegExp::Wildcard:
        return wc2rx(pattern, false);
        break;
    case QRegExp::WildcardUnix:
        return wc2rx(pattern, true);
        break;
#endif
    case QRegExp::FixedString:
        return QRegExp::escape(pattern);
        break;
    case QRegExp::W3CXmlSchema11:
    default:
        return pattern;
    }
}

wc2rx()

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

static

Definition at line 761 of file qregexp.cpp.

Referenced by qt_regexp_toCanonical().

{
    const int wclen = wc_str.length();
    QString rx;
    int i = 0;
    bool isEscaping = false; // the previous character is '\'
    const QChar *wc = wc_str.unicode();

    while (i < wclen) {
        const QChar c = wc[i++];
        switch (c.unicode()) {
        case '\\':
            if (enableEscaping) {
                if (isEscaping) {
                    rx += QLatin1String("\\\\");
                } // we insert the \\ later if necessary
                if (i == wclen) { // the end
                    rx += QLatin1String("\\\\");
                }
            } else {
                rx += QLatin1String("\\\\");
            }
            isEscaping = true;
            break;
        case '*':
            if (isEscaping) {
                rx += QLatin1String("\\*");
                isEscaping = false;
            } else {
                rx += QLatin1String(".*");
            }
            break;
        case '?':
            if (isEscaping) {
                rx += QLatin1String("\\?");
                isEscaping = false;
            } else {
                rx += QLatin1Char('.');
            }

            break;
        case '$':
        case '(':
        case ')':
        case '+':
        case '.':
        case '^':
        case '{':
        case '|':
        case '}':
            if (isEscaping) {
                isEscaping = false;
                rx += QLatin1String("\\\\");
            }
            rx += QLatin1Char('\\');
            rx += c;
            break;
         case '[':
            if (isEscaping) {
                isEscaping = false;
                rx += QLatin1String("\\[");
            } else {
                rx += c;
                if (wc[i] == QLatin1Char('^'))
                    rx += wc[i++];
                if (i < wclen) {
                    if (rx[i] == QLatin1Char(']'))
                        rx += wc[i++];
                    while (i < wclen && wc[i] != QLatin1Char(']')) {
                        if (wc[i] == QLatin1Char('\\'))
                            rx += QLatin1Char('\\');
                        rx += wc[i++];
                    }
                }
            }
             break;

        case ']':
            if(isEscaping){
                isEscaping = false;
                rx += QLatin1String("\\");
            }
            rx += c;
            break;

        default:
            if(isEscaping){
                isEscaping = false;
                rx += QLatin1String("\\\\");
            }
            rx += c;
        }
    }
    return rx;
}

Variable Documentation

EmptyCapture

const int EmptyCapture = INT_MAX

Definition at line 702 of file qregexp.cpp.

Referenced by QRegExpMatchState::match(), QRegExpMatchState::matchHere(), and QRegExpMatchState::testAnchor().

EOS

const int EOS = -1

Definition at line 705 of file qregexp.cpp.

Referenced by QRegExpEngine::getChar(), QRegExpEngine::getEscape(), and QRegExpEngine::getToken().

InftyLen

const int InftyLen = INT_MAX

Definition at line 703 of file qregexp.cpp.

Referenced by QRegExpEngine::Box::cat(), QRegExpEngine::Box::plus(), and QRegExpEngine::Box::set().

InftyRep

const int InftyRep = 1025

Definition at line 704 of file qregexp.cpp.

Referenced by QRegExpEngine::getRep(), QRegExpEngine::getToken(), and QRegExpEngine::parseFactor().

NoOccurrence

const int NoOccurrence = INT_MAX

Definition at line 701 of file qregexp.cpp.

Referenced by QRegExpEngine::badCharMatch(), QRegExpEngine::Box::Box(), QRegExpEngine::Box::cat(), QRegExpEngine::heuristicallyChooseHeuristic(), QRegExpCharClass::in(), QRegExpCharClass::QRegExpCharClass(), and QRegExpEngine::Box::setupHeuristics().

NumBadChars

const int NumBadChars = 64

Definition at line 698 of file qregexp.cpp.

Referenced by QRegExpCharClass::addCategories(), QRegExpCharClass::addRange(), QRegExpEngine::Box::Box(), QRegExpEngine::Box::cat(), QRegExpEngine::heuristicallyChooseHeuristic(), QRegExpEngine::Box::orx(), QRegExpCharClass::QRegExpCharClass(), QRegExpCharClass::setNegative(), QRegExpEngine::setup(), and QRegExpEngine::Box::setupHeuristics().