QRegExpMatchState Struct Reference

Public Functions
void	drain ()
void	match (const QChar *str, int len, int pos, bool minimal, bool oneTest, int caretIndex)
bool	matchHere ()
void	prepareForMatch (QRegExpEngine *eng)
	QRegExpMatchState ()
bool	testAnchor (int i, int a, const int *capBegin)
	~QRegExpMatchState ()

Public Variables
int *	bigArray
int *	capBegin
int *	capEnd
int *	captured
int	capturedSize
int	caretPos
int *	curCapBegin
int *	curCapEnd
int *	curStack
const QRegExpEngine *	eng
const QChar *	in
int *	inNextStack
int	len
int	matchLen
bool	minimal
int *	nextCapBegin
int *	nextCapEnd
int *	nextStack
int	oneTestMatchedLen
int	pos
QList< QVector< int > >	sleeping
int *	slideTab
int	slideTabSize
int *	tempCapBegin
int *	tempCapEnd

Detailed Description

Definition at line 902 of file qregexp.cpp.

Constructors and Destructors

QRegExpMatchState()

QRegExpMatchState::QRegExpMatchState ( )

inline

Definition at line 933 of file qregexp.cpp.

: bigArray(0), captured(0) {}

~QRegExpMatchState()

QRegExpMatchState::~QRegExpMatchState ( )

inline

Definition at line 934 of file qregexp.cpp.

{ free(bigArray); }

Functions

drain()

void QRegExpMatchState::drain ( )

inline

Definition at line 936 of file qregexp.cpp.

Referenced by invalidateEngine().

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

match()

void QRegExpMatchState::match	(	const QChar *	str,
		int	len,
		int	pos,
		bool	minimal,
		bool	oneTest,
		int	caretIndex
	)

Definition at line 1414 of file qregexp.cpp.

Referenced by testAnchor().

{
    bool matched = false;
    QChar char_null;

#ifndef QT_NO_REGEXP_OPTIM
    if (eng->trivial && !oneTest) {
        pos = qFindString(str0, len0, pos0, eng->goodStr.unicode(), eng->goodStr.length(), eng->cs);
        matchLen = eng->goodStr.length();
        matched = (pos != -1);
    } else
#endif
    {
        in = str0;
        if (in == 0)
            in = &char_null;
        pos = pos0;
        caretPos = caretIndex;
        len = len0;
        minimal = minimal0;
        matchLen = 0;
        oneTestMatchedLen = 0;

        if (eng->valid && pos >= 0 && pos <= len) {
#ifndef QT_NO_REGEXP_OPTIM
            if (oneTest) {
                matched = matchHere();
            } else {
                if (pos <= len - eng->minl) {
                    if (eng->caretAnchored) {
                        matched = matchHere();
                    } else if (eng->useGoodStringHeuristic) {
                        matched = eng->goodStringMatch(*this);
                    } else {
                        matched = eng->badCharMatch(*this);
                    }
                }
            }
#else
            matched = oneTest ? matchHere() : eng->bruteMatch(*this);
#endif
        }
    }

    if (matched) {
        int *c = captured;
        *c++ = pos;
        *c++ = matchLen;

        int numCaptures = (capturedSize - 2) >> 1;
#ifndef QT_NO_REGEXP_CAPTURE
        for (int i = 0; i < numCaptures; ++i) {
            int j = eng->captureForOfficialCapture.at(i);
            if (capBegin[j] != EmptyCapture) {
                int len = capEnd[j] - capBegin[j];
                *c++ = (len > 0) ? pos + capBegin[j] : 0;
                *c++ = len;
            } else {
                *c++ = -1;
                *c++ = -1;
            }
        }
#endif
    } else {
        // we rely on 2's complement here
        memset(captured, -1, capturedSize * sizeof(int));
    }
}

matchHere()

bool QRegExpMatchState::matchHere

(

)

Definition at line 1971 of file qregexp.cpp.

Referenced by QRegExpEngine::badCharMatch(), and QRegExpEngine::goodStringMatch().

{
    int ncur = 1, nnext = 0;
    int i = 0, j, k, m;
    bool stop = false;

    matchLen = -1;
    oneTestMatchedLen = -1;
    curStack[0] = QRegExpEngine::InitialState;

    int ncap = eng->ncap;
#ifndef QT_NO_REGEXP_CAPTURE
    if (ncap > 0) {
        for (j = 0; j < ncap; j++) {
            curCapBegin[j] = EmptyCapture;
            curCapEnd[j] = EmptyCapture;
        }
    }
#endif

#ifndef QT_NO_REGEXP_BACKREF
    while ((ncur > 0 || !sleeping.isEmpty()) && i <= len - pos && !stop)
#else
    while (ncur > 0 && i <= len - pos && !stop)
#endif
    {
        int ch = (i < len - pos) ? in[pos + i].unicode() : 0;
        for (j = 0; j < ncur; j++) {
            int cur = curStack[j];
            const QRegExpAutomatonState &scur = eng->s.at(cur);
            const QVector<int> &outs = scur.outs;
            for (k = 0; k < outs.size(); k++) {
                int next = outs.at(k);
                const QRegExpAutomatonState &snext = eng->s.at(next);
                bool inside = true;
#if !defined(QT_NO_REGEXP_BACKREF) && !defined(QT_NO_REGEXP_CAPTURE)
                int needSomeSleep = 0;
#endif

                /*
                  First, check if the anchors are anchored properly.
                */
                int a = scur.anchors.value(next);
                if (a != 0 && !testAnchor(i, a, curCapBegin + j * ncap))
                    inside = false;

                /*
                  If indeed they are, check if the input character is
                  correct for this transition.
                */
                if (inside) {
                    m = snext.match;
                    if ((m & (QRegExpEngine::CharClassBit | QRegExpEngine::BackRefBit)) == 0) {
                        if (eng->cs)
                            inside = (m == ch);
                        else
                            inside = (QChar(m).toLower() == QChar(ch).toLower());
                    } else if (next == QRegExpEngine::FinalState) {
                        matchLen = i;
                        stop = minimal;
                        inside = true;
                    } else if ((m & QRegExpEngine::CharClassBit) != 0) {
#ifndef QT_NO_REGEXP_CCLASS
                        const QRegExpCharClass &cc = eng->cl.at(m ^ QRegExpEngine::CharClassBit);
                        if (eng->cs)
                            inside = cc.in(ch);
                        else if (cc.negative())
                            inside = cc.in(QChar(ch).toLower()) &&
                                     cc.in(QChar(ch).toUpper());
                        else
                            inside = cc.in(QChar(ch).toLower()) ||
                                     cc.in(QChar(ch).toUpper());
#endif
#if !defined(QT_NO_REGEXP_BACKREF) && !defined(QT_NO_REGEXP_CAPTURE)
                    } else { /* ((m & QRegExpEngine::BackRefBit) != 0) */
                        int bref = m ^ QRegExpEngine::BackRefBit;
                        int ell = j * ncap + eng->captureForOfficialCapture.at(bref - 1);

                        inside = bref <= ncap && curCapBegin[ell] != EmptyCapture;
                        if (inside) {
                            if (eng->cs)
                                inside = (in[pos + curCapBegin[ell]] == QChar(ch));
                            else
                                inside = (in[pos + curCapBegin[ell]].toLower()
                                       == QChar(ch).toLower());
                        }

                        if (inside) {
                            int delta;
                            if (curCapEnd[ell] == EmptyCapture)
                                delta = i - curCapBegin[ell];
                            else
                                delta = curCapEnd[ell] - curCapBegin[ell];

                            inside = (delta <= len - (pos + i));
                            if (inside && delta > 1) {
                                int n = 1;
                                if (eng->cs) {
                                    while (n < delta) {
                                        if (in[pos + curCapBegin[ell] + n]
                                            != in[pos + i + n])
                                            break;
                                        ++n;
                                    }
                                } else {
                                    while (n < delta) {
                                        QChar a = in[pos + curCapBegin[ell] + n];
                                        QChar b = in[pos + i + n];
                                        if (a.toLower() != b.toLower())
                                            break;
                                        ++n;
                                    }
                                }
                                inside = (n == delta);
                                if (inside)
                                    needSomeSleep = delta - 1;
                            }
                        }
#endif
                    }
                }

                /*
                  We must now update our data structures.
                */
                if (inside) {
#ifndef QT_NO_REGEXP_CAPTURE
                    int *capBegin, *capEnd;
#endif
                    /*
                      If the next state was not encountered yet, all
                      is fine.
                    */
                    if ((m = inNextStack[next]) == -1) {
                        m = nnext++;
                        nextStack[m] = next;
                        inNextStack[next] = m;
#ifndef QT_NO_REGEXP_CAPTURE
                        capBegin = nextCapBegin + m * ncap;
                        capEnd = nextCapEnd + m * ncap;

                    /*
                      Otherwise, we'll first maintain captures in
                      temporary arrays, and decide at the end whether
                      it's best to keep the previous capture zones or
                      the new ones.
                    */
                    } else {
                        capBegin = tempCapBegin;
                        capEnd = tempCapEnd;
#endif
                    }

#ifndef QT_NO_REGEXP_CAPTURE
                    /*
                      Updating the capture zones is much of a task.
                    */
                    if (ncap > 0) {
                        memcpy(capBegin, curCapBegin + j * ncap, ncap * sizeof(int));
                        memcpy(capEnd, curCapEnd + j * ncap, ncap * sizeof(int));
                        int c = scur.atom, n = snext.atom;
                        int p = -1, q = -1;
                        int cap;

                        /*
                          Lemma 1. For any x in the range [0..nf), we
                          have f[x].parent < x.

                          Proof. By looking at startAtom(), it is
                          clear that cf < nf holds all the time, and
                          thus that f[nf].parent < nf.
                        */

                        /*
                          If we are reentering an atom, we empty all
                          capture zones inside it.
                        */
                        if ((q = scur.reenter.value(next)) != 0) {
                            QBitArray b(eng->nf, false);
                            b.setBit(q, true);
                            for (int ell = q + 1; ell < eng->nf; ell++) {
                                if (b.testBit(eng->f.at(ell).parent)) {
                                    b.setBit(ell, true);
                                    cap = eng->f.at(ell).capture;
                                    if (cap >= 0) {
                                        capBegin[cap] = EmptyCapture;
                                        capEnd[cap] = EmptyCapture;
                                    }
                                }
                            }
                            p = eng->f.at(q).parent;

                        /*
                          Otherwise, close the capture zones we are
                          leaving. We are leaving f[c].capture,
                          f[f[c].parent].capture,
                          f[f[f[c].parent].parent].capture, ...,
                          until f[x].capture, with x such that
                          f[x].parent is the youngest common ancestor
                          for c and n.

                          We go up along c's and n's ancestry until
                          we find x.
                        */
                        } else {
                            p = c;
                            q = n;
                            while (p != q) {
                                if (p > q) {
                                    cap = eng->f.at(p).capture;
                                    if (cap >= 0) {
                                        if (capBegin[cap] == i) {
                                            capBegin[cap] = EmptyCapture;
                                            capEnd[cap] = EmptyCapture;
                                        } else {
                                            capEnd[cap] = i;
                                        }
                                    }
                                    p = eng->f.at(p).parent;
                                } else {
                                    q = eng->f.at(q).parent;
                                }
                            }
                        }

                        /*
                          In any case, we now open the capture zones
                          we are entering. We work upwards from n
                          until we reach p (the parent of the atom we
                          reenter or the youngest common ancestor).
                        */
                        while (n > p) {
                            cap = eng->f.at(n).capture;
                            if (cap >= 0) {
                                capBegin[cap] = i;
                                capEnd[cap] = EmptyCapture;
                            }
                            n = eng->f.at(n).parent;
                        }
                        /*
                          If the next state was already in
                          nextStack, we must choose carefully which
                          capture zones we want to keep.
                        */
                        if (capBegin == tempCapBegin &&
                                isBetterCapture(ncap, capBegin, capEnd, nextCapBegin + m * ncap,
                                                nextCapEnd + m * ncap)) {
                            memcpy(nextCapBegin + m * ncap, capBegin, ncap * sizeof(int));
                            memcpy(nextCapEnd + m * ncap, capEnd, ncap * sizeof(int));
                        }
                    }
#ifndef QT_NO_REGEXP_BACKREF
                    /*
                      We are done with updating the capture zones.
                      It's now time to put the next state to sleep,
                      if it needs to, and to remove it from
                      nextStack.
                    */
                    if (needSomeSleep > 0) {
                        QVector<int> zzZ(2 + 2 * ncap);
                        zzZ[0] = i + needSomeSleep;
                        zzZ[1] = next;
                        if (ncap > 0) {
                            memcpy(zzZ.data() + 2, capBegin, ncap * sizeof(int));
                            memcpy(zzZ.data() + 2 + ncap, capEnd, ncap * sizeof(int));
                        }
                        inNextStack[nextStack[--nnext]] = -1;
                        sleeping.append(zzZ);
                    }
#endif
#endif
                }
            }
        }
#ifndef QT_NO_REGEXP_CAPTURE
        /*
          If we reached the final state, hurray! Copy the captured
          zone.
        */
        if (ncap > 0 && (m = inNextStack[QRegExpEngine::FinalState]) != -1) {
            memcpy(capBegin, nextCapBegin + m * ncap, ncap * sizeof(int));
            memcpy(capEnd, nextCapEnd + m * ncap, ncap * sizeof(int));
        }
#ifndef QT_NO_REGEXP_BACKREF
        /*
          It's time to wake up the sleepers.
        */
        j = 0;
        while (j < sleeping.count()) {
            if (sleeping.at(j)[0] == i) {
                const QVector<int> &zzZ = sleeping.at(j);
                int next = zzZ[1];
                const int *capBegin = zzZ.data() + 2;
                const int *capEnd = zzZ.data() + 2 + ncap;
                bool copyOver = true;

                if ((m = inNextStack[next]) == -1) {
                    m = nnext++;
                    nextStack[m] = next;
                    inNextStack[next] = m;
                } else {
                    copyOver = isBetterCapture(ncap, nextCapBegin + m * ncap, nextCapEnd + m * ncap,
                                               capBegin, capEnd);
                }
                if (copyOver) {
                    memcpy(nextCapBegin + m * ncap, capBegin, ncap * sizeof(int));
                    memcpy(nextCapEnd + m * ncap, capEnd, ncap * sizeof(int));
                }

                sleeping.removeAt(j);
            } else {
                ++j;
            }
        }
#endif
#endif
        for (j = 0; j < nnext; j++)
            inNextStack[nextStack[j]] = -1;

        // avoid needless iteration that confuses oneTestMatchedLen
        if (nnext == 1 && nextStack[0] == QRegExpEngine::FinalState
#ifndef QT_NO_REGEXP_BACKREF
             && sleeping.isEmpty()
#endif
           )
            stop = true;

        qSwap(curStack, nextStack);
#ifndef QT_NO_REGEXP_CAPTURE
        qSwap(curCapBegin, nextCapBegin);
        qSwap(curCapEnd, nextCapEnd);
#endif
        ncur = nnext;
        nnext = 0;
        ++i;
    }

#ifndef QT_NO_REGEXP_BACKREF
    /*
      If minimal matching is enabled, we might have some sleepers
      left.
    */
    if (!sleeping.isEmpty())
        sleeping.clear();
#endif

    oneTestMatchedLen = i - 1;
    return (matchLen >= 0);
}

prepareForMatch()

void QRegExpMatchState::prepareForMatch

(

QRegExpEngine *

eng

)

Definition at line 1367 of file qregexp.cpp.

Referenced by prepareEngine_helper(), prepareEngineForMatch(), and testAnchor().

{
    /*
      We use one QVector<int> for all the big data used a lot in
      matchHere() and friends.
    */
    int ns = eng->s.size(); // number of states
    int ncap = eng->ncap;
#ifndef QT_NO_REGEXP_OPTIM
    int newSlideTabSize = qMax(eng->minl + 1, 16);
#else
    int newSlideTabSize = 0;
#endif
    int numCaptures = eng->captureCount();
    int newCapturedSize = 2 + 2 * numCaptures;
    bigArray = q_check_ptr((int *)realloc(bigArray, ((3 + 4 * ncap) * ns + 4 * ncap + newSlideTabSize + newCapturedSize)*sizeof(int)));

    // set all internal variables only _after_ bigArray is realloc'ed
    // to prevent a broken regexp in oom case

    slideTabSize = newSlideTabSize;
    capturedSize = newCapturedSize;
    inNextStack = bigArray;
    memset(inNextStack, -1, ns * sizeof(int));
    curStack = inNextStack + ns;
    nextStack = inNextStack + 2 * ns;

    curCapBegin = inNextStack + 3 * ns;
    nextCapBegin = curCapBegin + ncap * ns;
    curCapEnd = curCapBegin + 2 * ncap * ns;
    nextCapEnd = curCapBegin + 3 * ncap * ns;

    tempCapBegin = curCapBegin + 4 * ncap * ns;
    tempCapEnd = tempCapBegin + ncap;
    capBegin = tempCapBegin + 2 * ncap;
    capEnd = tempCapBegin + 3 * ncap;

    slideTab = tempCapBegin + 4 * ncap;
    captured = slideTab + slideTabSize;
    memset(captured, -1, capturedSize*sizeof(int));
    this->eng = eng;
}

testAnchor()

bool QRegExpMatchState::testAnchor	(	int	i,
		int	a,
		const int *	capBegin
	)

Definition at line 1804 of file qregexp.cpp.

{
    int j;

#ifndef QT_NO_REGEXP_ANCHOR_ALT
    if ((a & QRegExpEngine::Anchor_Alternation) != 0)
        return testAnchor(i, eng->aa.at(a ^ QRegExpEngine::Anchor_Alternation).a, capBegin)
               || testAnchor(i, eng->aa.at(a ^ QRegExpEngine::Anchor_Alternation).b, capBegin);
#endif

    if ((a & QRegExpEngine::Anchor_Caret) != 0) {
        if (pos + i != caretPos)
            return false;
    }
    if ((a & QRegExpEngine::Anchor_Dollar) != 0) {
        if (pos + i != len)
            return false;
    }
#ifndef QT_NO_REGEXP_ESCAPE
    if ((a & (QRegExpEngine::Anchor_Word | QRegExpEngine::Anchor_NonWord)) != 0) {
        bool before = false;
        bool after = false;
        if (pos + i != 0)
            before = isWord(in[pos + i - 1]);
        if (pos + i != len)
            after = isWord(in[pos + i]);
        if ((a & QRegExpEngine::Anchor_Word) != 0 && (before == after))
            return false;
        if ((a & QRegExpEngine::Anchor_NonWord) != 0 && (before != after))
            return false;
    }
#endif
#ifndef QT_NO_REGEXP_LOOKAHEAD
    if ((a & QRegExpEngine::Anchor_LookaheadMask) != 0) {
        const QVector<QRegExpLookahead *> &ahead = eng->ahead;
        for (j = 0; j < ahead.size(); j++) {
            if ((a & (QRegExpEngine::Anchor_FirstLookahead << j)) != 0) {
                QRegExpMatchState matchState;
                matchState.prepareForMatch(ahead[j]->eng);
                matchState.match(in + pos + i, len - pos - i, 0,
                    true, true, caretPos - pos - i);
                if ((matchState.captured[0] == 0) == ahead[j]->neg)
                    return false;
            }
        }
    }
#endif
#ifndef QT_NO_REGEXP_CAPTURE
#ifndef QT_NO_REGEXP_BACKREF
    for (j = 0; j < eng->nbrefs; j++) {
        if ((a & (QRegExpEngine::Anchor_BackRef1Empty << j)) != 0) {
            int i = eng->captureForOfficialCapture.at(j);
            if (capBegin[i] != EmptyCapture)
                return false;
        }
    }
#endif
#endif
    return true;
}

Properties

bigArray

int* QRegExpMatchState::bigArray

Definition at line 909 of file qregexp.cpp.

capBegin

int* QRegExpMatchState::capBegin

Definition at line 919 of file qregexp.cpp.

capEnd

int* QRegExpMatchState::capEnd

Definition at line 920 of file qregexp.cpp.

captured

int* QRegExpMatchState::captured

Definition at line 922 of file qregexp.cpp.

Referenced by QRegExp::operator=(), and testAnchor().

capturedSize

int QRegExpMatchState::capturedSize

Definition at line 924 of file qregexp.cpp.

caretPos

int QRegExpMatchState::caretPos

Definition at line 906 of file qregexp.cpp.

curCapBegin

int* QRegExpMatchState::curCapBegin

Definition at line 913 of file qregexp.cpp.

curCapEnd

int* QRegExpMatchState::curCapEnd

Definition at line 915 of file qregexp.cpp.

curStack

int* QRegExpMatchState::curStack

Definition at line 911 of file qregexp.cpp.

eng

const QRegExpEngine* QRegExpMatchState::eng

Definition at line 931 of file qregexp.cpp.

in

const QChar* QRegExpMatchState::in

Definition at line 904 of file qregexp.cpp.

Referenced by QRegExpEngine::badCharMatch(), and QRegExpEngine::goodStringMatch().

inNextStack

int* QRegExpMatchState::inNextStack

Definition at line 910 of file qregexp.cpp.

len

int QRegExpMatchState::len

Definition at line 907 of file qregexp.cpp.

Referenced by QRegExpEngine::badCharMatch(), and QRegExpEngine::goodStringMatch().

matchLen

int QRegExpMatchState::matchLen

Definition at line 928 of file qregexp.cpp.

minimal

bool QRegExpMatchState::minimal

Definition at line 908 of file qregexp.cpp.

nextCapBegin

int* QRegExpMatchState::nextCapBegin

Definition at line 914 of file qregexp.cpp.

nextCapEnd

int* QRegExpMatchState::nextCapEnd

Definition at line 916 of file qregexp.cpp.

nextStack

int* QRegExpMatchState::nextStack

Definition at line 912 of file qregexp.cpp.

oneTestMatchedLen

int QRegExpMatchState::oneTestMatchedLen

Definition at line 929 of file qregexp.cpp.

pos

int QRegExpMatchState::pos

Definition at line 905 of file qregexp.cpp.

Referenced by QRegExpEngine::badCharMatch(), and QRegExpEngine::goodStringMatch().

sleeping

QList<QVector<int> > QRegExpMatchState::sleeping

Definition at line 926 of file qregexp.cpp.

slideTab

int* QRegExpMatchState::slideTab

Definition at line 921 of file qregexp.cpp.

Referenced by QRegExpEngine::badCharMatch().

slideTabSize

int QRegExpMatchState::slideTabSize

Definition at line 923 of file qregexp.cpp.

Referenced by QRegExpEngine::badCharMatch().

tempCapBegin

int* QRegExpMatchState::tempCapBegin

Definition at line 917 of file qregexp.cpp.

tempCapEnd

int* QRegExpMatchState::tempCapEnd

Definition at line 918 of file qregexp.cpp.

---

The documentation for this struct was generated from the following file:

• /src/corelib/tools/qregexp.cpp