qregexp.cpp

奇趣公司比较新的qt/emd版本

*/

const int NumBadChars = 64;
#define BadChar(ch) ((ch).unicode() % NumBadChars)

const int NoOccurrence = INT_MAX;
const int EmptyCapture = INT_MAX;
const int InftyLen = INT_MAX;
const int InftyRep = 1025;
const int EOS = -1;

static bool isWord(QChar ch)
{
    return ch.isLetterOrNumber() || ch.isMark() || ch == QLatin1Char('_');
}

/*
  Merges two vectors of ints and puts the result into the first
  one.
*/
static void mergeInto(QVector<int> *a, const QVector<int> &b)
{
    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;
    }
}

#ifndef QT_NO_REGEXP_WILDCARD
/*
  Translates a wildcard pattern to an equivalent regular expression
  pattern (e.g., *.cpp to .*\.cpp).
*/
static QString wc2rx(const QString &wc_str)
{
    int wclen = wc_str.length();
    QString rx;
    int i = 0;
    const QChar *wc = wc_str.unicode();
    while (i < wclen) {
        QChar c = wc[i++];
        switch (c.unicode()) {
        case '*':
            rx += QLatin1String(".*");
            break;
        case '?':
            rx += QLatin1Char('.');
            break;
        case '$':
        case '(':
        case ')':
        case '+':
        case '.':
        case '\\':
        case '^':
        case '{':
        case '|':
        case '}':
            rx += QLatin1Char('\\');
            rx += c;
            break;
        case '[':
            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;
        default:
            rx += c;
        }
    }
    return rx;
}
#endif

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

/*
    The QRegExpEngineKey struct uniquely identifies an engine.
*/
struct QRegExpEngineKey
{
    QString pattern;
    QRegExp::PatternSyntax patternSyntax;
    Qt::CaseSensitivity cs;

    inline QRegExpEngineKey(const QString &pattern, QRegExp::PatternSyntax patternSyntax,
                            Qt::CaseSensitivity cs)
        : pattern(pattern), patternSyntax(patternSyntax), cs(cs) {}

    inline void clear() {
        pattern.clear();
        patternSyntax = QRegExp::RegExp;
        cs = Qt::CaseSensitive;
    }
};

bool operator==(const QRegExpEngineKey &key1, const QRegExpEngineKey &key2)
{
    return key1.pattern == key2.pattern && key1.patternSyntax == key2.patternSyntax
           && key1.cs == key2.cs;
}

class QRegExpEngine;

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

/*
  This is the engine state during matching.
*/
struct QRegExpMatchState
{
    const QString *str; // a pointer to the input QString
    const QChar *in; // a pointer to the input string data
    int pos; // the current position in the string
    int caretPos;
    int len; // the length of the input string
    bool minimal; // minimal matching?
    QVector<int> bigArray; // big QVector<int> array
    int *inNextStack; // is state is nextStack?
    int *curStack; // stack of current states
    int *nextStack; // stack of next states
    int *curCapBegin; // start of current states' captures
    int *nextCapBegin; // start of next states' captures
    int *curCapEnd; // end of current states' captures
    int *nextCapEnd; // end of next states' captures
    int *tempCapBegin; // start of temporary captures
    int *tempCapEnd; // end of temporary captures
    int *capBegin; // start of captures for a next state
    int *capEnd; // end of captures for a next state
    int *slideTab; // bump-along slide table for bad-character heuristic
    int slideTabSize; // size of slide table
#ifndef QT_NO_REGEXP_BACKREF
    QList<QVector<int> > sleeping; // list of back-reference sleepers
#endif
    int matchLen; // length of match
    int oneTestMatchedLen; // length of partial match

    QVector<int> captured; // what match() returned last
    const QRegExpEngine *eng;

    inline QRegExpMatchState() { captured.fill(-1, 2); }

    void drain() { bigArray.clear(); } // to save memory
    void prepareForMatch(QRegExpEngine *eng);
    void match(const QString &str, int pos, bool minimal, bool oneTest, int caretIndex);
    bool matchHere();
    bool testAnchor(int i, int a, const int *capBegin);
};

/*
  The struct QRegExpAutomatonState represents one state in a modified NFA. The
  input characters matched are stored in the state instead of on
  the transitions, something possible for an automaton
  constructed from a regular expression.
*/
struct QRegExpAutomatonState
{
#ifndef QT_NO_REGEXP_CAPTURE
    int atom; // which atom does this state belong to?
#endif
    int match; // what does it match? (see CharClassBit and BackRefBit)
    QVector<int> outs; // out-transitions
    QMap<int, int> reenter; // atoms reentered when transiting out
    QMap<int, int> anchors; // anchors met when transiting out

    inline QRegExpAutomatonState() { }
#ifndef QT_NO_REGEXP_CAPTURE
    inline QRegExpAutomatonState(int a, int m)
        : atom(a), match(m) { }
#else
    inline QRegExpAutomatonState(int m)
        : match(m) { }
#endif
};

Q_DECLARE_TYPEINFO(QRegExpAutomatonState, Q_MOVABLE_TYPE);

/*
  The struct QRegExpCharClassRange represents a range of characters (e.g.,
  [0-9] denotes range 48 to 57).
*/
struct QRegExpCharClassRange
{
    ushort from; // 48
    ushort len; // 10
};

Q_DECLARE_TYPEINFO(QRegExpCharClassRange, Q_PRIMITIVE_TYPE);

#ifndef QT_NO_REGEXP_CAPTURE
/*
  The struct QRegExpAtom represents one node in the hierarchy of regular
  expression atoms.
*/
struct QRegExpAtom
{
    enum { NoCapture = -1, OfficialCapture = -2, UnofficialCapture = -3 };

    int parent; // index of parent in array of atoms
    int capture; // index of capture, from 1 to ncap - 1
};

Q_DECLARE_TYPEINFO(QRegExpAtom, Q_PRIMITIVE_TYPE);
#endif

struct QRegExpLookahead;

#ifndef QT_NO_REGEXP_ANCHOR_ALT
/*
  The struct QRegExpAnchorAlternation represents a pair of anchors with
  OR semantics.
*/
struct QRegExpAnchorAlternation
{
    int a; // this anchor...
    int b; // ...or this one
};

Q_DECLARE_TYPEINFO(QRegExpAnchorAlternation, Q_PRIMITIVE_TYPE);
#endif

#ifndef QT_NO_REGEXP_CCLASS
/*
  The class QRegExpCharClass represents a set of characters, such as can
  be found in regular expressions (e.g., [a-z] denotes the set
  {a, b, ..., z}).
*/
class QRegExpCharClass
{
public:
    QRegExpCharClass();
    inline QRegExpCharClass(const QRegExpCharClass &cc) { operator=(cc); }

    QRegExpCharClass &operator=(const QRegExpCharClass &cc);

    void clear();
    bool negative() const { return n; }
    void setNegative(bool negative);
    void addCategories(int cats);
    void addRange(ushort from, ushort to);
    void addSingleton(ushort ch) { addRange(ch, ch); }

    bool in(QChar ch) const;
#ifndef QT_NO_REGEXP_OPTIM
    const QVector<int> &firstOccurrence() const { return occ1; }
#endif

#if defined(QT_DEBUG)
    void dump() const;
#endif

private:
    int c; // character classes
    QVector<QRegExpCharClassRange> r; // character ranges
    bool n; // negative?
#ifndef QT_NO_REGEXP_OPTIM
    QVector<int> occ1; // first-occurrence array
#endif
};
#else
struct QRegExpCharClass
{
    int dummy;

#ifndef QT_NO_REGEXP_OPTIM
    QRegExpCharClass() { occ1.fill(0, NumBadChars); }

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

Q_DECLARE_TYPEINFO(QRegExpCharClass, Q_MOVABLE_TYPE);

/*
  The QRegExpEngine class encapsulates a modified nondeterministic
  finite automaton (NFA).
*/
class QRegExpEngine
{
public:
    QRegExpEngine(Qt::CaseSensitivity cs, bool greedyQuantifiers)
        : cs(cs), greedyQuantifiers(greedyQuantifiers) { setup(); }

    QRegExpEngine(const QRegExpEngineKey &key);
    ~QRegExpEngine();

    bool isValid() const { return valid; }
    const QString &errorString() const { return yyError; }
    int numCaptures() const { return officialncap; }

    int createState(QChar ch);
    int createState(const QRegExpCharClass &cc);
#ifndef QT_NO_REGEXP_BACKREF
    int createState(int bref);
#endif

    void addCatTransitions(const QVector<int> &from, const QVector<int> &to);
#ifndef QT_NO_REGEXP_CAPTURE
    void addPlusTransitions(const QVector<int> &from, const QVector<int> &to, int atom);
#endif

#ifndef QT_NO_REGEXP_ANCHOR_ALT
    int anchorAlternation(int a, int b);
    int anchorConcatenation(int a, int b);
#else
    int anchorAlternation(int a, int b) { return a & b; }
    int anchorConcatenation(int a, int b) { return a | b; }
#endif
    void addAnchors(int from, int to, int a);

#ifndef QT_NO_REGEXP_OPTIM
    void heuristicallyChooseHeuristic();
#endif

#if defined(QT_DEBUG)
    void dump() const;
#endif

    int ref;