qregexp.cpp

Go to the documentation of this file.

/****************************************************************************
** $Id: qregexp.cpp,v 1.2 2003/07/10 02:40:12 llornkcor Exp $
**
** Implementation of QRegExp class
**
** Created : 950126
**
** Copyright (C) 1992-2000 Trolltech AS.  All rights reserved.
**
** This file is part of the tools module of the Qt GUI Toolkit.
**
** This file may be distributed under the terms of the Q Public License
** as defined by Trolltech AS of Norway and appearing in the file
** LICENSE.QPL included in the packaging of this file.
**
** This file may be distributed and/or modified under the terms of the
** GNU General Public License version 2 as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL included in the
** packaging of this file.
**
** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition
** licenses may use this file in accordance with the Qt Commercial License
** Agreement provided with the Software.
**
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
**
** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
**   information about Qt Commercial License Agreements.
** See http://www.trolltech.com/qpl/ for QPL licensing information.
** See http://www.trolltech.com/gpl/ for GPL licensing information.
**
** Contact info@trolltech.com if any conditions of this licensing are
** not clear to you.
**
**********************************************************************/

#include "qregexp.h"

#ifndef QT_NO_REGEXP

#include "qmemarray.h"
#include "qbitarray.h"
#include "qcache.h"
#include "qcleanuphandler.h"
#include "qintdict.h"
#include "qmap.h"
#include "qptrvector.h"
#include "qstring.h"
#include "qtl.h"

#ifdef QT_THREAD_SUPPORT
#include "qmutexpool_p.h"
#endif // QT_THREAD_SUPPORT

#undef QT_TRANSLATE_NOOP
#define QT_TRANSLATE_NOOP( context, sourceText ) sourceText

#include <limits.h>

// 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" )

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

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 == QChar( '_' );
}

/*
  Merges two QMemArrays of ints and puts the result into the first one.
*/
static void mergeInto( QMemArray<int> *a, const QMemArray<int>& b )
{
    int asize = a->size();
    int bsize = b.size();
    if ( asize == 0 ) {
        *a = b.copy();
#ifndef QT_NO_REGEXP_OPTIM
    } else if ( bsize == 1 && (*a)[asize - 1] < b[0] ) {
        a->resize( asize + 1 );
        (*a)[asize] = b[0];
#endif
    } else if ( bsize >= 1 ) {
        int csize = asize + bsize;
        QMemArray<int> c( csize );
        int i = 0, j = 0, k = 0;
        while ( i < asize ) {
            if ( j < bsize ) {
                if ( (*a)[i] == b[j] ) {
                    i++;
                    csize--;
                } else if ( (*a)[i] < b[j] ) {
                    c[k++] = (*a)[i++];
                } else {
                    c[k++] = b[j++];
                }
            } else {
                memcpy( c.data() + k, (*a).data() + i,
                        (asize - i) * sizeof(int) );
                break;
            }
        }
        c.resize( csize );
        if ( j < bsize )
            memcpy( c.data() + k, b.data() + j, (bsize - j) * sizeof(int) );
        *a = c;
    }
}

/*
  Merges two disjoint QMaps of (int, int) pairs and puts the result into the
  first one.
*/
static void mergeInto( QMap<int, int> *a, const QMap<int, int>& b )
{
    QMap<int, int>::ConstIterator it;
    for ( it = b.begin(); it != b.end(); ++it )
        a->insert( it.key(), *it );
}

/*
  Returns the value associated to key k in QMap m of (int, int) pairs, or 0 if
  no such value is explicitly present.
*/
static int at( const QMap<int, int>& m, int k )
{
    QMap<int, int>::ConstIterator it = m.find( k );
    if ( it == m.end() )
        return 0;
    else
        return *it;
}

#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 = QString::fromLatin1( "" );
    int i = 0;
    const QChar *wc = wc_str.unicode();
    while ( i < wclen ) {
        QChar c = wc[i++];
        switch ( c.unicode() ) {
        case '*':
            rx += QString::fromLatin1( ".*" );
            break;
        case '?':
            rx += QChar( '.' );
            break;
        case '$':
        case '(':
        case ')':
        case '+':
        case '.':
        case '\\':
        case '^':
        case '{':
        case '|':
        case '}':
            rx += QChar( '\\' );
            rx += c;
            break;
        case '[':
            rx += c;
            if ( wc[i] == QChar('^') )
                rx += wc[i++];
            if ( i < wclen ) {
                if ( rx[i] == ']' )
                    rx += wc[i++];
                while ( i < wclen && wc[i] != QChar(']') ) {
                    if ( wc[i] == '\\' )
                        rx += QChar( '\\' );
                    rx += wc[i++];
                }
            }
            break;
        default:
            rx += c;
        }
    }
    return rx;
}
#endif

/*
  The class QRegExpEngine encapsulates a modified nondeterministic
  finite automaton (NFA).
*/
class QRegExpEngine : public QShared
{
public:
#ifndef QT_NO_REGEXP_CCLASS
    /*
      The class CharClass represents a set of characters, such as can
      be found in regular expressions (e.g., [a-z] denotes the set
      {a, b, ..., z}).
    */
    class CharClass
    {
    public:
        CharClass();
        CharClass( const CharClass& cc ) { operator=( cc ); }

        CharClass& operator=( const CharClass& 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 QMemArray<int>& firstOccurrence() const { return occ1; }
#endif

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

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

        int c; // character classes
        QMemArray<Range> r; // character ranges
        bool n; // negative?
#ifndef QT_NO_REGEXP_OPTIM
        QMemArray<int> occ1; // first-occurrence array
#endif
    };
#else
    struct CharClass
    {
        int dummy;

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

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

    QRegExpEngine( bool caseSensitive ) { setup( caseSensitive ); }
    QRegExpEngine( const QString& rx, bool caseSensitive );
#ifndef QT_NO_REGEXP_OPTIM
    ~QRegExpEngine();
#endif

    bool isValid() const { return valid; }
    const QString& errorString() const { return yyError; }
    bool caseSensitive() const { return cs; }
    int numCaptures() const { return officialncap; }
    QMemArray<int> match( const QString& str, int pos, bool minimal,
                          bool oneTest, int caretIndex );
    int matchedLength() const { return mmMatchedLen; }

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

    void addCatTransitions( const QMemArray<int>& from,
                            const QMemArray<int>& to );
#ifndef QT_NO_REGEXP_CAPTURE
    void addPlusTransitions( const QMemArray<int>& from,
                             const QMemArray<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 setupGoodStringHeuristic( int earlyStart, int lateStart,
                                   const QString& str );
    void setupBadCharHeuristic( int minLen, const QMemArray<int>& firstOcc );
    void heuristicallyChooseHeuristic();
#endif

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

private:
    enum { CharClassBit = 0x10000, BackRefBit = 0x20000 };

    /*
      The struct State 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 State
    {
#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)
        QMemArray<int> outs; // out-transitions
        QMap<int, int> *reenter; // atoms reentered when transiting out
        QMap<int, int> *anchors; // anchors met when transiting out

#ifndef QT_NO_REGEXP_CAPTURE
        State( int a, int m )
            : atom( a ), match( m ), reenter( 0 ), anchors( 0 ) { }
#else
        State( int m )
            : match( m ), reenter( 0 ), anchors( 0 ) { }
#endif
        ~State() { delete reenter; delete anchors; }
    };

#ifndef QT_NO_REGEXP_LOOKAHEAD
    /*
      The struct Lookahead represents a lookahead a la Perl (e.g., (?=foo) and
      (?!bar)).
    */
    struct Lookahead
    {
        QRegExpEngine *eng; // NFA representing the embedded regular expression
        bool neg; // negative lookahead?

        Lookahead( QRegExpEngine *eng0, bool neg0 )
            : eng( eng0 ), neg( neg0 ) { }
        ~Lookahead() { delete eng; }
    };
#endif

#ifndef QT_NO_REGEXP_CAPTURE
    /*
      The struct Atom represents one node in the hierarchy of regular
      expression atoms.
    */
    struct Atom
    {
        int parent; // index of parent in array of atoms
        int capture; // index of capture, from 1 to ncap
    };
#endif

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

    enum { InitialState = 0, FinalState = 1 };
    void setup( bool caseSensitive );
    int setupState( int match );

    /*
      Let's hope that 13 lookaheads and 14 back-references are
      enough.
     */
    enum { MaxLookaheads = 13, MaxBackRefs = 14 };
    enum { Anchor_Dollar = 0x00000001, Anchor_Caret = 0x00000002,
           Anchor_Word = 0x00000004, Anchor_NonWord = 0x00000008,
           Anchor_FirstLookahead = 0x00000010,
           Anchor_BackRef1Empty = Anchor_FirstLookahead << MaxLookaheads,
           Anchor_BackRef0Empty = Anchor_BackRef1Empty >> 1,
           Anchor_Alternation = Anchor_BackRef1Empty << MaxBackRefs,

           Anchor_LookaheadMask = ( Anchor_FirstLookahead - 1 ) ^
                   ( (Anchor_FirstLookahead << MaxLookaheads) - 1 ) };
#ifndef QT_NO_REGEXP_CAPTURE
    int startAtom( bool capture );
    void finishAtom( int atom ) { cf = f[atom].parent; }
#endif

#ifndef QT_NO_REGEXP_LOOKAHEAD
    int addLookahead( QRegExpEngine *eng, bool negative );
#endif

#ifndef QT_NO_REGEXP_CAPTURE
    bool isBetterCapture( const int *begin1, const int *end1, const int *begin2,
                          const int *end2 );
#endif
    bool testAnchor( int i, int a, const int *capBegin );

#ifndef QT_NO_REGEXP_OPTIM
    bool goodStringMatch();
    bool badCharMatch();
#else
    bool bruteMatch();
#endif
    bool matchHere();

    QPtrVector<State> s; // array of states
    int ns; // number of states
#ifndef QT_NO_REGEXP_CAPTURE
    QMemArray<Atom> f; // atom hierarchy
    int nf; // number of atoms
    int cf; // current atom
#endif
    int officialncap; // number of captures, seen from the outside
    int ncap; // number of captures, seen from the inside
#ifndef QT_NO_REGEXP_CCLASS
    QPtrVector<CharClass> cl; // array of character classes
#endif
#ifndef QT_NO_REGEXP_LOOKAHEAD
    QPtrVector<Lookahead> ahead; // array of lookaheads
#endif
#ifndef QT_NO_REGEXP_ANCHOR_ALT
    QMemArray<AnchorAlternation> aa; // array of (a, b) pairs of anchors
#endif
#ifndef QT_NO_REGEXP_OPTIM
    bool caretAnchored; // does the regexp start with ^?
#endif
    bool valid; // is the regular expression valid?
    bool cs; // case sensitive?
#ifndef QT_NO_REGEXP_BACKREF
    int nbrefs; // number of back-references
#endif

#ifndef QT_NO_REGEXP_OPTIM
    bool useGoodStringHeuristic; // use goodStringMatch? otherwise badCharMatch

    int goodEarlyStart; // the index where goodStr can first occur in a match
    int goodLateStart; // the index where goodStr can last occur in a match
    QString goodStr; // the string that any match has to contain

    int minl; // the minimum length of a match
    QMemArray<int> occ1; // first-occurrence array
#endif

    /*
      The class Box is an abstraction for a regular expression
      fragment. It can also be seen as one node in the syntax tree of
      a regular expression with synthetized attributes.

      It's interface is ugly for performance reasons.
    */
    class Box
    {
    public:
        Box( QRegExpEngine *engine );
        Box( const Box& b ) { operator=( b ); }

        Box& operator=( const Box& b );

        void clear() { operator=(Box(eng)); }
        void set( QChar ch );
        void set( const CharClass& cc );
#ifndef QT_NO_REGEXP_BACKREF
        void set( int bref );
#endif

        void cat( const Box& b );
        void orx( const Box& b );
        void plus( int atom );
        void opt();
        void catAnchor( int a );
#ifndef QT_NO_REGEXP_OPTIM
        void setupHeuristics();
#endif

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

    private:
        void addAnchorsToEngine( const Box& to ) const;

        QRegExpEngine *eng; // the automaton under construction
        QMemArray<int> ls; // the left states (firstpos)
        QMemArray<int> rs; // the right states (lastpos)
        QMap<int, int> lanchors; // the left anchors
        QMap<int, int> ranchors; // the right anchors
        int skipanchors; // the anchors to match if the box is skipped

#ifndef QT_NO_REGEXP_OPTIM
        int earlyStart; // the index where str can first occur
        int lateStart; // the index where str can last occur
        QString str; // a string that has to occur in any match
        QString leftStr; // a string occurring at the left of this box
        QString rightStr; // a string occurring at the right of this box
        int maxl; // the maximum length of this box (possibly InftyLen)
#endif

        int minl; // the minimum length of this box
#ifndef QT_NO_REGEXP_OPTIM
        QMemArray<int> occ1; // first-occurrence array
#endif
    };
    friend class Box;

    /*
      This is the lexical analyzer for regular expressions.
    */
    enum { Tok_Eos, Tok_Dollar, Tok_LeftParen, Tok_MagicLeftParen,
           Tok_PosLookahead, Tok_NegLookahead, Tok_RightParen, Tok_CharClass,
           Tok_Caret, Tok_Quantifier, Tok_Bar, Tok_Word, Tok_NonWord,
           Tok_Char = 0x10000, Tok_BackRef = 0x20000 };
    int getChar();
    int getEscape();
#ifndef QT_NO_REGEXP_INTERVAL
    int getRep( int def );
#endif
#ifndef QT_NO_REGEXP_LOOKAHEAD
    void skipChars( int n );
#endif
    void error( const char *msg );
    void startTokenizer( const QChar *rx, int len );
    int getToken();

    const QChar *yyIn; // a pointer to the input regular expression pattern
    int yyPos0; // the position of yyTok in the input pattern
    int yyPos; // the position of the next character to read
    int yyLen; // the length of yyIn
    int yyCh; // the last character read
    CharClass *yyCharClass; // attribute for Tok_CharClass tokens
    int yyMinRep; // attribute for Tok_Quantifier
    int yyMaxRep; // ditto
    QString yyError; // syntax error or overflow during parsing?

    /*
      This is the syntactic analyzer for regular expressions.
    */
    int parse( const QChar *rx, int len );
    void parseAtom( Box *box );
    void parseFactor( Box *box );
    void parseTerm( Box *box );
    void parseExpression( Box *box );

    int yyTok; // the last token read
    bool yyMayCapture; // set this to FALSE to disable capturing

    /*
      This is the engine state during matching.
    */
    const QString *mmStr; // a pointer to the input QString
    const QChar *mmIn; // a pointer to the input string data
    int mmPos; // the current position in the string
    int mmCaretPos;
    int mmLen; // the length of the input string
    bool mmMinimal; // minimal matching?
    QMemArray<int> mmCaptured; // an array of pairs (start, len)
    QMemArray<int> mmCapturedNoMatch; // an array of pairs (-1, -1)
    QMemArray<int> mmBigArray; // big QMemArray<int> array
    int *mmInNextStack; // is state is mmNextStack?
    int *mmCurStack; // stack of current states
    int *mmNextStack; // stack of next states
    int *mmCurCapBegin; // start of current states' captures
    int *mmNextCapBegin; // start of next states' captures
    int *mmCurCapEnd; // end of current states' captures
    int *mmNextCapEnd; // end of next states' captures
    int *mmTempCapBegin; // start of temporary captures
    int *mmTempCapEnd; // end of temporary captures
    int *mmCapBegin; // start of captures for a next state
    int *mmCapEnd; // end of captures for a next state
    int *mmSlideTab; // bump-along slide table for bad-character heuristic
    int mmSlideTabSize; // size of slide table
#ifndef QT_NO_REGEXP_BACKREF
    QIntDict<int> mmSleeping; // dictionary of back-reference sleepers
#endif
    int mmMatchLen; // length of match
    int mmMatchedLen; // length of partial match
};

QRegExpEngine::QRegExpEngine( const QString& rx, bool caseSensitive )
#ifndef QT_NO_REGEXP_BACKREF
    : mmSleeping( 101 )
#endif
{
    setup( caseSensitive );
    valid = ( parse(rx.unicode(), rx.length()) == (int) rx.length() );
    if ( !valid )
        error( RXERR_LEFTDELIM );
}

#ifndef QT_NO_REGEXP_OPTIM
QRegExpEngine::~QRegExpEngine()
{
}
#endif

/*
  Tries to match in str and returns an array of (begin, length) pairs
  for captured text. If there is no match, all pairs are (-1, -1).
*/
QMemArray<int> QRegExpEngine::match( const QString& str, int pos, bool minimal,
                                     bool oneTest, int caretIndex )
{
    mmStr = &str;
    mmIn = str.unicode();
    if ( mmIn == 0 )
        mmIn = &QChar::null;
    mmPos = pos;
    mmCaretPos = caretIndex;
    mmLen = str.length();
    mmMinimal = minimal;
    mmMatchLen = 0;
    mmMatchedLen = 0;

    bool matched = FALSE;
    if ( valid && mmPos >= 0 && mmPos <= mmLen ) {
#ifndef QT_NO_REGEXP_OPTIM
        if ( oneTest ) {
            matched = matchHere();
        } else {
            if ( mmPos <= mmLen - minl ) {
                if ( caretAnchored ) {
                    matched = matchHere();
                } else if ( useGoodStringHeuristic ) {
                    matched = goodStringMatch();
                } else {
                    matched = badCharMatch();
                }
            }
        }
#else
        matched = oneTest ? matchHere() : bruteMatch();
#endif
    }

    if ( matched ) {
        mmCaptured.detach();
        mmCaptured[0] = mmPos;
        mmCaptured[1] = mmMatchLen;
        for ( int j = 0; j < officialncap; j++ ) {
            int len = mmCapEnd[j] - mmCapBegin[j];
            mmCaptured[2 + 2 * j] = len > 0 ? mmPos + mmCapBegin[j] : 0;
            mmCaptured[2 + 2 * j + 1] = len;
        }
        return mmCaptured;
    } else {
        return mmCapturedNoMatch;
    }
}

/*
  The three following functions add one state to the automaton and
  return the number of the state.
*/

int QRegExpEngine::createState( QChar ch )
{
    return setupState( ch.unicode() );
}

int QRegExpEngine::createState( const CharClass& cc )
{
#ifndef QT_NO_REGEXP_CCLASS
    int n = cl.size();
    cl.resize( n + 1 );
    cl.insert( n, new CharClass(cc) );
    return setupState( CharClassBit | n );
#else
    Q_UNUSED( cc );
    return setupState( CharClassBit );
#endif
}

#ifndef QT_NO_REGEXP_BACKREF
int QRegExpEngine::createState( int bref )
{
    if ( bref > nbrefs ) {
        nbrefs = bref;
        if ( nbrefs > MaxBackRefs ) {
            error( RXERR_LIMIT );
            return 0;
        }
    }
    return setupState( BackRefBit | bref );
}
#endif

/*
  The two following functions add a transition between all pairs of
  states (i, j) where i is fond in from, and j is found in to.

  Cat-transitions are distinguished from plus-transitions for
  capturing.
*/

void QRegExpEngine::addCatTransitions( const QMemArray<int>& from,
                                       const QMemArray<int>& to )
{
    for ( int i = 0; i < (int) from.size(); i++ ) {
        State *st = s[from[i]];
        mergeInto( &st->outs, to );
    }
}

#ifndef QT_NO_REGEXP_CAPTURE
void QRegExpEngine::addPlusTransitions( const QMemArray<int>& from,
                                        const QMemArray<int>& to, int atom )
{
    for ( int i = 0; i < (int) from.size(); i++ ) {
        State *st = s[from[i]];
        QMemArray<int> oldOuts = st->outs.copy();
        mergeInto( &st->outs, to );
        if ( f[atom].capture >= 0 ) {
            if ( st->reenter == 0 )
                st->reenter = new QMap<int, int>;
            for ( int j = 0; j < (int) to.size(); j++ ) {
                if ( !st->reenter->contains(to[j]) &&
                     oldOuts.bsearch(to[j]) < 0 )
                    st->reenter->insert( to[j], atom );
            }
        }
    }
}
#endif

#ifndef QT_NO_REGEXP_ANCHOR_ALT
/*
  Returns an anchor that means a OR b.
*/
int QRegExpEngine::anchorAlternation( int a, int b )
{
    if ( ((a & b) == a || (a & b) == b) && ((a | b) & Anchor_Alternation) == 0 )
        return a & b;

    int n = aa.size();
#ifndef QT_NO_REGEXP_OPTIM
    if ( n > 0 && aa[n - 1].a == a && aa[n - 1].b == b )
        return Anchor_Alternation | ( n - 1 );
#endif

    aa.resize( n + 1 );
    aa[n].a = a;
    aa[n].b = b;
    return Anchor_Alternation | n;
}

/*
  Returns an anchor that means a AND b.
*/
int QRegExpEngine::anchorConcatenation( int a, int b )
{
    if ( ((a | b) & Anchor_Alternation) == 0 )
        return a | b;
    if ( (b & Anchor_Alternation) != 0 )
        qSwap( a, b );

    int aprime = anchorConcatenation( aa[a ^ Anchor_Alternation].a, b );
    int bprime = anchorConcatenation( aa[a ^ Anchor_Alternation].b, b );
    return anchorAlternation( aprime, bprime );
}
#endif

/*
  Adds anchor a on a transition caracterised by its from state and
  its to state.
*/
void QRegExpEngine::addAnchors( int from, int to, int a )
{
    State *st = s[from];
    if ( st->anchors == 0 )
        st->anchors = new QMap<int, int>;
    if ( st->anchors->contains(to) )
        a = anchorAlternation( (*st->anchors)[to], a );
    st->anchors->insert( to, a );
}

#ifndef QT_NO_REGEXP_OPTIM
/*
  The two following functions provide the engine with the information
  needed by its matching heuristics.
*/

void QRegExpEngine::setupGoodStringHeuristic( int earlyStart, int lateStart,
                                              const QString& str )
{
    goodEarlyStart = earlyStart;
    goodLateStart = lateStart;
    goodStr = cs ? str : str.lower();
}

void QRegExpEngine::setupBadCharHeuristic( int minLen,
                                           const QMemArray<int>& firstOcc )
{
    minl = minLen;
    if ( cs ) {
        occ1 = firstOcc;
    } else {
        occ1.fill( 0, NumBadChars );
    }
}

/*
  This function chooses between the good-string and the bad-character
  heuristics. It computes two scores and chooses the heuristic with
  the highest score.

  Here are some common-sense constraints on the scores that should be
  respected if the formulas are ever modified: (1) If goodStr is
  empty, the good-string heuristic scores 0. (2) If the search is
  case insensitive, the good-string heuristic should be used, unless
  it scores 0. (Case insensitivity turns all entries of occ1 to 0.)
  (3) If (goodLateStart - goodEarlyStart) is big, the good-string
  heuristic should score less.
*/
void QRegExpEngine::heuristicallyChooseHeuristic()
{
    int i;

    if ( minl == 0 )
        return;

    /*
      Magic formula:  The good string has to constitute a good
      proportion of the minimum-length string, and appear at a
      more-or-less known index.
    */
    int goodStringScore = ( 64 * goodStr.length() / minl ) -
                          ( goodLateStart - goodEarlyStart );

    /*
      Less magic formula:  We pick a couple of characters at random,
      and check whether they are good or bad.
    */
    int badCharScore = 0;
    int step = QMAX( 1, NumBadChars / 32 );
    for ( i = 1; i < NumBadChars; i += step ) {
        if ( occ1[i] == NoOccurrence )
            badCharScore += minl;
        else
            badCharScore += occ1[i];
    }
    badCharScore /= minl;

    useGoodStringHeuristic = ( goodStringScore > badCharScore );
}
#endif

#if defined(QT_DEBUG)
void QRegExpEngine::dump() const
{
    int i, j;
    qDebug( "Case %ssensitive engine", cs ? "" : "in" );
    qDebug( "  States" );
    for ( i = 0; i < ns; i++ ) {
        qDebug( "  %d%s", i,
                i == InitialState ? " (initial)" :
                i == FinalState ? " (final)" : "" );
#ifndef QT_NO_REGEXP_CAPTURE
        qDebug( "    in atom %d", s[i]->atom );
#endif
        int m = s[i]->match;
        if ( (m & CharClassBit) != 0 ) {
            qDebug( "    match character class %d", m ^ CharClassBit );
#ifndef QT_NO_REGEXP_CCLASS
            cl[m ^ CharClassBit]->dump();
#else
            qDebug( "    negative character class" );
#endif
        } else if ( (m & BackRefBit) != 0 ) {
            qDebug( "    match back-reference %d", m ^ BackRefBit );
        } else if ( m >= 0x20 && m <= 0x7e ) {
            qDebug( "    match 0x%.4x (%c)", m, m );
        } else {
            qDebug( "    match 0x%.4x", m );
        }
        for ( j = 0; j < (int) s[i]->outs.size(); j++ ) {
            int next = s[i]->outs[j];
            qDebug( "    -> %d", next );
            if ( s[i]->reenter != 0 && s[i]->reenter->contains(next) )
                qDebug( "       [reenter %d]", (*s[i]->reenter)[next] );
            if ( s[i]->anchors != 0 && at(*s[i]->anchors, next) != 0 )
                qDebug( "       [anchors 0x%.8x]", (*s[i]->anchors)[next] );
        }
    }
#ifndef QT_NO_REGEXP_CAPTURE
    if ( nf > 0 ) {
        qDebug( "  Atom    Parent  Capture" );
        for ( i = 0; i < nf; i++ )
            qDebug( "  %6d  %6d  %6d", i, f[i].parent, f[i].capture );
    }
#endif
#ifndef QT_NO_REGEXP_ANCHOR_ALT
    for ( i = 0; i < (int) aa.size(); i++ )
        qDebug( "  Anchor alternation 0x%.8x: 0x%.8x 0x%.9x", i, aa[i].a,
                aa[i].b );
#endif
}
#endif

void QRegExpEngine::setup( bool caseSensitive )
{
    s.setAutoDelete( TRUE );
    s.resize( 32 );
    ns = 0;
#ifndef QT_NO_REGEXP_CAPTURE
    f.resize( 32 );
    nf = 0;
    cf = -1;
#endif
    officialncap = 0;
    ncap = 0;
#ifndef QT_NO_REGEXP_CCLASS
    cl.setAutoDelete( TRUE );
#endif
#ifndef QT_NO_REGEXP_LOOKAHEAD
    ahead.setAutoDelete( TRUE );
#endif
#ifndef QT_NO_REGEXP_OPTIM
    caretAnchored = TRUE;
#endif
    valid = FALSE;
    cs = caseSensitive;
#ifndef QT_NO_REGEXP_BACKREF
    nbrefs = 0;
#endif
#ifndef QT_NO_REGEXP_OPTIM
    useGoodStringHeuristic = FALSE;
    minl = 0;
    occ1.fill( 0, NumBadChars );
#endif
    mmCapturedNoMatch.fill( -1, 2 );
}

int QRegExpEngine::setupState( int match )
{
    if ( (ns & (ns + 1)) == 0 && ns + 1 >= (int) s.size() )
        s.resize( (ns + 1) << 1 );
#ifndef QT_NO_REGEXP_CAPTURE
    s.insert( ns, new State(cf, match) );
#else
    s.insert( ns, new State(match) );
#endif
    return ns++;
}

#ifndef QT_NO_REGEXP_CAPTURE
/*
  Functions startAtom() and finishAtom() should be called to delimit
  atoms. When a state is created, it is assigned to the current atom.
  The information is later used for capturing.
*/
int QRegExpEngine::startAtom( bool capture )
{
    if ( (nf & (nf + 1)) == 0 && nf + 1 >= (int) f.size() )
        f.resize( (nf + 1) << 1 );
    f[nf].parent = cf;
    cf = nf++;
    f[cf].capture = capture ? ncap++ : -1;
    return cf;
}
#endif

#ifndef QT_NO_REGEXP_LOOKAHEAD
/*
  Creates a lookahead anchor.
*/
int QRegExpEngine::addLookahead( QRegExpEngine *eng, bool negative )
{
    int n = ahead.size();
    if ( n == MaxLookaheads ) {
        error( RXERR_LIMIT );
        return 0;
    }
    ahead.resize( n + 1 );
    ahead.insert( n, new Lookahead(eng, negative) );
    return Anchor_FirstLookahead << n;
}
#endif

#ifndef QT_NO_REGEXP_CAPTURE
/*
  We want the longest leftmost captures.
*/
bool QRegExpEngine::isBetterCapture( const int *begin1, const int *end1,
                                     const int *begin2, const int *end2 )
{
    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 (like a party)

        if ( delta != 0 )
            return delta > 0;
    }
    return FALSE;
}
#endif

/*
  Returns TRUE if anchor a matches at position mmPos + i in the input
  string, otherwise FALSE.
*/
bool QRegExpEngine::testAnchor( int i, int a, const int *capBegin )
{
    int j;

#ifndef QT_NO_REGEXP_ANCHOR_ALT
    if ( (a & Anchor_Alternation) != 0 ) {
        return testAnchor( i, aa[a ^ Anchor_Alternation].a, capBegin ) ||
               testAnchor( i, aa[a ^ Anchor_Alternation].b, capBegin );
    }
#endif

    if ( (a & Anchor_Caret) != 0 ) {
        if ( mmPos + i != mmCaretPos )
            return FALSE;
    }
    if ( (a & Anchor_Dollar) != 0 ) {
        if ( mmPos + i != mmLen )
            return FALSE;
    }
#ifndef QT_NO_REGEXP_ESCAPE
    if ( (a & (Anchor_Word | Anchor_NonWord)) != 0 ) {
        bool before = FALSE;
        bool after = FALSE;
        if ( mmPos + i != 0 )
            before = isWord( mmIn[mmPos + i - 1] );
        if ( mmPos + i != mmLen )
            after = isWord( mmIn[mmPos + i] );
        if ( (a & Anchor_Word) != 0 && (before == after) )
            return FALSE;
        if ( (a & Anchor_NonWord) != 0 && (before != after) )
            return FALSE;
    }
#endif
#ifndef QT_NO_REGEXP_LOOKAHEAD
    bool catchx = TRUE;

    if ( (a & Anchor_LookaheadMask) != 0 ) {
        QConstString cstr = QConstString( (QChar *) mmIn + mmPos + i,
                                           mmLen - mmPos - i );
        for ( j = 0; j < (int) ahead.size(); j++ ) {
            if ( (a & (Anchor_FirstLookahead << j)) != 0 ) {
                catchx = ahead[j]->eng->match( cstr.string(), 0, TRUE, TRUE,
                                               mmCaretPos - mmPos - i )[0] == 0;
                if ( catchx == ahead[j]->neg )
                    return FALSE;
            }
        }
    }
#endif
#ifndef QT_NO_REGEXP_CAPTURE
#ifndef QT_NO_REGEXP_BACKREF
    for ( j = 0; j < nbrefs; j++ ) {
        if ( (a & (Anchor_BackRef1Empty << j)) != 0 ) {
            if ( capBegin[j] != EmptyCapture )
                return FALSE;
        }
    }
#endif
#endif
    return TRUE;
}

#ifndef QT_NO_REGEXP_OPTIM
/*
  The three following functions are what Jeffrey Friedl would call
  transmissions (or bump-alongs). Using one or the other should make
  no difference except in performance.
*/

bool QRegExpEngine::goodStringMatch()
{
    int k = mmPos + goodEarlyStart;

    while ( (k = mmStr->find(goodStr, k, cs)) != -1 ) {
        int from = k - goodLateStart;
        int to = k - goodEarlyStart;
        if ( from > mmPos )
            mmPos = from;

        while ( mmPos <= to ) {
            if ( matchHere() )
                return TRUE;
            mmPos++;
        }
        k++;
    }
    return FALSE;
}

bool QRegExpEngine::badCharMatch()
{
    int slideHead = 0;
    int slideNext = 0;
    int i;
    int lastPos = mmLen - minl;
    memset( mmSlideTab, 0, mmSlideTabSize * sizeof(int) );

    /*
      Set up the slide table, used for the bad-character heuristic,
      using the table of first occurrence of each character.
    */
    for ( i = 0; i < minl; i++ ) {
        int sk = occ1[BadChar(mmIn[mmPos + i])];
        if ( sk == NoOccurrence )
            sk = i + 1;
        if ( sk > 0 ) {
            int k = i + 1 - sk;
            if ( k < 0 ) {
                sk = i + 1;
                k = 0;
            }
            if ( sk > mmSlideTab[k] )
                mmSlideTab[k] = sk;
        }
    }

    if ( mmPos > lastPos )
        return FALSE;

    for ( ;; ) {
        if ( ++slideNext >= mmSlideTabSize )
            slideNext = 0;
        if ( mmSlideTab[slideHead] > 0 ) {
            if ( mmSlideTab[slideHead] - 1 > mmSlideTab[slideNext] )
                mmSlideTab[slideNext] = mmSlideTab[slideHead] - 1;
            mmSlideTab[slideHead] = 0;
        } else {
            if ( matchHere() )
                return TRUE;
        }

        if ( mmPos == lastPos )
            break;

        /*
          Update the slide table. This code has much in common with
          the initialization code.
        */
        int sk = occ1[BadChar(mmIn[mmPos + minl])];
        if ( sk == NoOccurrence ) {
            mmSlideTab[slideNext] = minl;
        } else if ( sk > 0 ) {
            int k = slideNext + minl - sk;
            if ( k >= mmSlideTabSize )
                k -= mmSlideTabSize;
            if ( sk > mmSlideTab[k] )
                mmSlideTab[k] = sk;
        }
        slideHead = slideNext;
        mmPos++;
    }
    return FALSE;
}
#else
bool QRegExpEngine::bruteMatch()
{
    while ( mmPos <= mmLen ) {
        if ( matchHere() )
            return TRUE;
        mmPos++;
    }
    return FALSE;
}
#endif

/*
  Here's the core of the engine. It tries to do a match here and now.
*/
bool QRegExpEngine::matchHere()
{
    int ncur = 1, nnext = 0;
    int i = 0, j, k, m;
    bool stop = FALSE;

    mmMatchLen = -1;
    mmMatchedLen = -1;
    mmCurStack[0] = InitialState;

#ifndef QT_NO_REGEXP_CAPTURE
    if ( ncap > 0 ) {
        for ( j = 0; j < ncap; j++ ) {
            mmCurCapBegin[j] = EmptyCapture;
            mmCurCapEnd[j] = EmptyCapture;
        }
    }
#endif

#ifndef QT_NO_REGEXP_BACKREF
    int *zzZ = 0;

    while ( (ncur > 0 || !mmSleeping.isEmpty()) && i <= mmLen - mmPos &&
            !stop )
#else
    while ( ncur > 0 && i <= mmLen - mmPos && !stop )
#endif
    {
        int ch = ( i < mmLen - mmPos ) ? mmIn[mmPos + i].unicode() : 0;
        for ( j = 0; j < ncur; j++ ) {
            int cur = mmCurStack[j];
            State *scur = s[cur];
            QMemArray<int>& outs = scur->outs;
            for ( k = 0; k < (int) outs.size(); k++ ) {
                int next = outs[k];
                State *snext = s[next];
                bool in = TRUE;
#ifndef QT_NO_REGEXP_BACKREF
                int needSomeSleep = 0;
#endif

                /*
                  First, check if the anchors are anchored properly.
                */
                if ( scur->anchors != 0 ) {
                    int a = at( *scur->anchors, next );
                    if ( a != 0 && !testAnchor(i, a, mmCurCapBegin + j * ncap) )
                        in = FALSE;
                }
                /*
                  If indeed they are, check if the input character is
                  correct for this transition.
                */
                if ( in ) {
                    m = snext->match;
                    if ( (m & (CharClassBit | BackRefBit)) == 0 ) {
                        if ( cs )
                            in = ( m == ch );
                        else
                            in = ( QChar(m).lower() == QChar(ch).lower() );
                    } else if ( next == FinalState ) {
                        mmMatchLen = i;
                        stop = mmMinimal;
                        in = TRUE;
                    } else if ( (m & CharClassBit) != 0 ) {
#ifndef QT_NO_REGEXP_CCLASS
                        const CharClass *cc = cl[m ^ CharClassBit];
                        if ( cs )
                            in = cc->in( ch );
                        else if ( cc->negative() )
                            in = cc->in( QChar(ch).lower() ) &&
                                 cc->in( QChar(ch).upper() );
                        else
                            in = cc->in( QChar(ch).lower() ) ||
                                 cc->in( QChar(ch).upper() );
#endif
#ifndef QT_NO_REGEXP_BACKREF
                    } else { /* ( (m & BackRefBit) != 0 ) */
                        int bref = m ^ BackRefBit;
                        int ell = j * ncap + ( bref - 1 );

                        in = bref <= ncap && mmCurCapBegin[ell] != EmptyCapture;
                        if ( in ) {
                            if ( cs )
                                in = ( mmIn[mmPos + mmCurCapBegin[ell]]
                                       == QChar(ch) );
                            else
                                in = ( mmIn[mmPos + mmCurCapBegin[ell]].lower()
                                       == QChar(ch).lower() );
                        }

                        if ( in ) {
                            int delta;
                            if ( mmCurCapEnd[ell] == EmptyCapture )
                                delta = i - mmCurCapBegin[ell];
                            else
                                delta = mmCurCapEnd[ell] - mmCurCapBegin[ell];

                            in = ( delta <= mmLen - (mmPos + i) );
                            if ( in && delta > 1 ) {
                                int n = 1;
                                if ( cs ) {
                                    while ( n < delta ) {
                                        if ( mmIn[mmPos +
                                                  mmCurCapBegin[ell] + n] !=
                                             mmIn[mmPos + i + n] )
                                            break;
                                        n++;
                                    }
                                } else {
                                    while ( n < delta ) {
                                        QChar a = mmIn[mmPos +
                                                       mmCurCapBegin[ell] + n];
                                        QChar b = mmIn[mmPos + i + n];
                                        if ( a.lower() != b.lower() )
                                            break;
                                        n++;
                                    }
                                }
                                in = ( n == delta );
                                if ( in )
                                    needSomeSleep = delta - 1;
                            }
                        }
#endif
                    }
                }

                /*
                  We must now update our data structures.
                */
                if ( in ) {
#ifndef QT_NO_REGEXP_CAPTURE
                    int *capBegin, *capEnd;
#endif
                    /*
                      If the next state was not encountered yet, all
                      is fine.
                    */
                    if ( (m = mmInNextStack[next]) == -1 ) {
                        m = nnext++;
                        mmNextStack[m] = next;
                        mmInNextStack[next] = m;
#ifndef QT_NO_REGEXP_CAPTURE
                        capBegin = mmNextCapBegin + m * ncap;
                        capEnd = mmNextCapEnd + 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 = mmTempCapBegin;
                        capEnd = mmTempCapEnd;
#endif
                    }

#ifndef QT_NO_REGEXP_CAPTURE
                    /*
                      Updating the capture zones is much of a task.
                    */
                    if ( ncap > 0 ) {
                        memcpy( capBegin, mmCurCapBegin + j * ncap,
                                ncap * sizeof(int) );
                        memcpy( capEnd, mmCurCapEnd + 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 ( scur->reenter != 0 &&
                             (q = at(*scur->reenter, next)) != 0 ) {
                            QBitArray b;
                            b.fill( FALSE, nf );
                            b.setBit( q, TRUE );
                            for ( int ell = q + 1; ell < nf; ell++ ) {
                                if ( b.testBit(f[ell].parent) ) {
                                    b.setBit( ell, TRUE );
                                    cap = f[ell].capture;
                                    if ( cap >= 0 ) {
                                        capBegin[cap] = EmptyCapture;
                                        capEnd[cap] = EmptyCapture;
                                    }
                                }
                            }
                            p = f[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 = f[p].capture;
                                    if ( cap >= 0 ) {
                                        if ( capBegin[cap] == i ) {
                                            capBegin[cap] = EmptyCapture;
                                            capEnd[cap] = EmptyCapture;
                                        } else {
                                            capEnd[cap] = i;
                                        }
                                    }
                                    p = f[p].parent;
                                } else {
                                    q = f[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 = f[n].capture;
                            if ( cap >= 0 ) {
                                capBegin[cap] = i;
                                capEnd[cap] = EmptyCapture;
                            }
                            n = f[n].parent;
                        }
                        /*
                          If the next state was already in
                          mmNextStack, we must choose carefully which
                          capture zones we want to keep.
                        */
                        if ( capBegin == mmTempCapBegin &&
                             isBetterCapture(capBegin, capEnd,
                                             mmNextCapBegin + m * ncap,
                                             mmNextCapEnd + m * ncap) ) {
                            memcpy( mmNextCapBegin + m * ncap, capBegin,
                                    ncap * sizeof(int) );
                            memcpy( mmNextCapEnd + 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
                      mmNextStack.
                    */
                    if ( needSomeSleep > 0 ) {
                        zzZ = new int[1 + 2 * ncap];
                        zzZ[0] = next;
                        if ( ncap > 0 ) {
                            memcpy( zzZ + 1, capBegin, ncap * sizeof(int) );
                            memcpy( zzZ + 1 + ncap, capEnd,
                                    ncap * sizeof(int) );
                        }
                        mmInNextStack[mmNextStack[--nnext]] = -1;
                        mmSleeping.insert( i + needSomeSleep, zzZ );
                    }
#endif
#endif
                }
            }
        }
#ifndef QT_NO_REGEXP_CAPTURE
        /*
          If we reached the final state, hurray! Copy the captured
          zone.
        */
        if ( ncap > 0 && (m = mmInNextStack[FinalState]) != -1 ) {
            memcpy( mmCapBegin, mmNextCapBegin + m * ncap, ncap * sizeof(int) );
            memcpy( mmCapEnd, mmNextCapEnd + m * ncap, ncap * sizeof(int) );
        }
#ifndef QT_NO_REGEXP_BACKREF
        /*
          It's time to wake up the sleepers.
        */
        if ( !mmSleeping.isEmpty() ) {
            while ( (zzZ = mmSleeping.take(i)) != 0 ) {
                int next = zzZ[0];
                int *capBegin = zzZ + 1;
                int *capEnd = zzZ + 1 + ncap;
                bool copyOver = TRUE;

                if ( (m = mmInNextStack[zzZ[0]]) == -1 ) {
                    m = nnext++;
                    mmNextStack[m] = next;
                    mmInNextStack[next] = m;
                } else {
                    copyOver = isBetterCapture( mmNextCapBegin + m * ncap,
                                                mmNextCapEnd + m * ncap,
                                                capBegin, capEnd );
                }
                if ( copyOver ) {
                    memcpy( mmNextCapBegin + m * ncap, capBegin,
                            ncap * sizeof(int) );
                    memcpy( mmNextCapEnd + m * ncap, capEnd,
                            ncap * sizeof(int) );
                }
                delete[] zzZ;
            }
        }
#endif
#endif
        for ( j = 0; j < nnext; j++ )
            mmInNextStack[mmNextStack[j]] = -1;

        // avoid needless iteration that confuses mmMatchedLen
        if ( nnext == 1 && mmNextStack[0] == FinalState
#ifndef QT_NO_REGEXP_BACKREF
             && mmSleeping.isEmpty()
#endif
             )
            stop = TRUE;

        qSwap( mmCurStack, mmNextStack );
#ifndef QT_NO_REGEXP_CAPTURE
        qSwap( mmCurCapBegin, mmNextCapBegin );
        qSwap( mmCurCapEnd, mmNextCapEnd );
#endif
        ncur = nnext;
        nnext = 0;
        i++;
    }

#ifndef QT_NO_REGEXP_BACKREF
    /*
      If minimal matching is enabled, we might have some sleepers
      left.
    */
    while ( !mmSleeping.isEmpty() ) {
        zzZ = mmSleeping.take( *QIntDictIterator<int>(mmSleeping) );
        delete[] zzZ;
    }
#endif

    mmMatchedLen = i - 1;
    return ( mmMatchLen >= 0 );
}

#ifndef QT_NO_REGEXP_CCLASS

QRegExpEngine::CharClass::CharClass()
    : c( 0 ), n( FALSE )
{
#ifndef QT_NO_REGEXP_OPTIM
    occ1.fill( NoOccurrence, NumBadChars );
#endif
}

QRegExpEngine::CharClass& QRegExpEngine::CharClass::operator=(
        const CharClass& cc )
{
    c = cc.c;
    r = cc.r.copy();
    n = cc.n;
#ifndef QT_NO_REGEXP_OPTIM
    occ1 = cc.occ1;
#endif
    return *this;
}

void QRegExpEngine::CharClass::clear()
{
    c = 0;
    r.resize( 0 );
    n = FALSE;
}

void QRegExpEngine::CharClass::setNegative( bool negative )
{
    n = negative;
#ifndef QT_NO_REGEXP_OPTIM
    occ1.fill( 0, NumBadChars );
#endif
}

void QRegExpEngine::CharClass::addCategories( int cats )
{
    c |= cats;
#ifndef QT_NO_REGEXP_OPTIM
    occ1.fill( 0, NumBadChars );
#endif
}

void QRegExpEngine::CharClass::addRange( ushort from, ushort to )
{
    if ( from > to )
        qSwap( from, to );
    int m = r.size();
    r.resize( m + 1 );
    r[m].from = from;
    r[m].to = to;

#ifndef QT_NO_REGEXP_OPTIM
    int i;

    if ( to - from < NumBadChars ) {
        occ1.detach();
        if ( from % NumBadChars <= to % NumBadChars ) {
            for ( i = from % NumBadChars; i <= to % NumBadChars; i++ )
                occ1[i] = 0;
        } else {
            for ( i = 0; i <= to % NumBadChars; i++ )
                occ1[i] = 0;
            for ( i = from % NumBadChars; i < NumBadChars; i++ )
                occ1[i] = 0;
        }
    } else {
        occ1.fill( 0, NumBadChars );
    }
#endif
}

bool QRegExpEngine::CharClass::in( QChar ch ) const
{
#ifndef QT_NO_REGEXP_OPTIM
    if ( occ1[BadChar(ch)] == NoOccurrence )
        return n;
#endif

    if ( c != 0 && (c & (1 << (int) ch.category())) != 0 )
        return !n;
    for ( int i = 0; i < (int) r.size(); i++ ) {
        if ( ch.unicode() >= r[i].from && ch.unicode() <= r[i].to )
            return !n;
    }
    return n;
}

#if defined(QT_DEBUG)
void QRegExpEngine::CharClass::dump() const
{
    int i;
    qDebug( "    %stive character class", n ? "nega" : "posi" );
#ifndef QT_NO_REGEXP_CCLASS
    if ( c != 0 )
        qDebug( "      categories 0x%.8x", c );
#endif
    for ( i = 0; i < (int) r.size(); i++ )
        qDebug( "      0x%.4x through 0x%.4x", r[i].from, r[i].to );
}
#endif
#endif

QRegExpEngine::Box::Box( QRegExpEngine *engine )
    : eng( engine ), skipanchors( 0 )
#ifndef QT_NO_REGEXP_OPTIM
      , earlyStart( 0 ), lateStart( 0 ), maxl( 0 )
#endif
{
#ifndef QT_NO_REGEXP_OPTIM
    occ1.fill( NoOccurrence, NumBadChars );
#endif
    minl = 0;
}

QRegExpEngine::Box& QRegExpEngine::Box::operator=( const Box& b )
{
    eng = b.eng;
    ls = b.ls;
    rs = b.rs;
    lanchors = b.lanchors;
    ranchors = b.ranchors;
    skipanchors = b.skipanchors;
#ifndef QT_NO_REGEXP_OPTIM
    earlyStart = b.earlyStart;
    lateStart = b.lateStart;
    str = b.str;
    leftStr = b.leftStr;
    rightStr = b.rightStr;
    maxl = b.maxl;
    occ1 = b.occ1;
#endif
    minl = b.minl;
    return *this;
}

void QRegExpEngine::Box::set( QChar ch )
{
    ls.resize( 1 );
    ls[0] = eng->createState( ch );
    rs = ls;
    rs.detach();
#ifndef QT_NO_REGEXP_OPTIM
    str = ch;
    leftStr = ch;
    rightStr = ch;
    maxl = 1;
    occ1.detach();
    occ1[BadChar(ch)] = 0;
#endif
    minl = 1;
}

void QRegExpEngine::Box::set( const CharClass& cc )
{
    ls.resize( 1 );
    ls[0] = eng->createState( cc );
    rs = ls;
    rs.detach();
#ifndef QT_NO_REGEXP_OPTIM
    maxl = 1;
    occ1 = cc.firstOccurrence();
#endif
    minl = 1;
}

#ifndef QT_NO_REGEXP_BACKREF
void QRegExpEngine::Box::set( int bref )
{
    ls.resize( 1 );
    ls[0] = eng->createState( bref );
    rs = ls;
    rs.detach();
    if ( bref >= 1 && bref <= MaxBackRefs )
        skipanchors = Anchor_BackRef0Empty << bref;
#ifndef QT_NO_REGEXP_OPTIM
    maxl = InftyLen;
#endif
    minl = 0;
}
#endif

void QRegExpEngine::Box::cat( const Box& b )
{
    eng->addCatTransitions( rs, b.ls );
    addAnchorsToEngine( b );
    if ( minl == 0 ) {
        mergeInto( &lanchors, b.lanchors );
        if ( skipanchors != 0 ) {
            for ( int i = 0; i < (int) b.ls.size(); i++ ) {
                int a = eng->anchorConcatenation( at(lanchors, b.ls[i]),
                                                  skipanchors );
                lanchors.insert( b.ls[i], a );
            }
        }
        mergeInto( &ls, b.ls );
    }
    if ( b.minl == 0 ) {
        mergeInto( &ranchors, b.ranchors );
        if ( b.skipanchors != 0 ) {
            for ( int i = 0; i < (int) rs.size(); i++ ) {
                int a = eng->anchorConcatenation( at(ranchors, rs[i]),
                                                  b.skipanchors );
                ranchors.insert( rs[i], a );
            }
        }
        mergeInto( &rs, b.rs );
    } else {
        ranchors = b.ranchors;
        rs = b.rs;
    }

#ifndef QT_NO_REGEXP_OPTIM
    if ( maxl != InftyLen ) {
        if ( rightStr.length() + b.leftStr.length() >
             QMAX(str.length(), b.str.length()) ) {
            earlyStart = minl - rightStr.length();
            lateStart = maxl - rightStr.length();
            str = rightStr + b.leftStr;
        } else if ( b.str.length() > str.length() ) {
            earlyStart = minl + b.earlyStart;
            lateStart = maxl + b.lateStart;
            str = b.str;
        }
    }

    if ( (int) leftStr.length() == maxl )
        leftStr += b.leftStr;
    if ( (int) b.rightStr.length() == b.maxl )
        rightStr += b.rightStr;
    else
        rightStr = b.rightStr;

    if ( maxl == InftyLen || b.maxl == InftyLen )
        maxl = InftyLen;
    else
        maxl += b.maxl;

    occ1.detach();
    for ( int i = 0; i < NumBadChars; i++ ) {
        if ( b.occ1[i] != NoOccurrence && minl + b.occ1[i] < occ1[i] )
            occ1[i] = minl + b.occ1[i];
    }
#endif

    minl += b.minl;
    if ( minl == 0 )
        skipanchors = eng->anchorConcatenation( skipanchors, b.skipanchors );
    else
        skipanchors = 0;
}

void QRegExpEngine::Box::orx( const Box& b )
{
    mergeInto( &ls, b.ls );
    mergeInto( &lanchors, b.lanchors );
    mergeInto( &rs, b.rs );
    mergeInto( &ranchors, b.ranchors );

    if ( b.minl == 0 ) {
        if ( minl == 0 )
            skipanchors = eng->anchorAlternation( skipanchors, b.skipanchors );
        else
            skipanchors = b.skipanchors;
    }

#ifndef QT_NO_REGEXP_OPTIM
    occ1.detach();
    for ( int i = 0; i < NumBadChars; i++ ) {
        if ( occ1[i] > b.occ1[i] )
            occ1[i] = b.occ1[i];
    }
    earlyStart = 0;
    lateStart = 0;
    str = QString();
    leftStr = QString();
    rightStr = QString();
    if ( b.maxl > maxl )
        maxl = b.maxl;
#endif
    if ( b.minl < minl )
        minl = b.minl;
}

void QRegExpEngine::Box::plus( int atom )
{
#ifndef QT_NO_REGEXP_CAPTURE
    eng->addPlusTransitions( rs, ls, atom );
#else
    Q_UNUSED( atom );
    eng->addCatTransitions( rs, ls );
#endif
    addAnchorsToEngine( *this );
#ifndef QT_NO_REGEXP_OPTIM
    maxl = InftyLen;
#endif
}

void QRegExpEngine::Box::opt()
{
#ifndef QT_NO_REGEXP_OPTIM
    earlyStart = 0;
    lateStart = 0;
    str = QString();
    leftStr = QString();
    rightStr = QString();
#endif
    skipanchors = 0;
    minl = 0;
}

void QRegExpEngine::Box::catAnchor( int a )
{
    if ( a != 0 ) {
        for ( int i = 0; i < (int) rs.size(); i++ ) {
            a = eng->anchorConcatenation( at(ranchors, rs[i]), a );
            ranchors.insert( rs[i], a );
        }
        if ( minl == 0 )
            skipanchors = eng->anchorConcatenation( skipanchors, a );
    }
}

#ifndef QT_NO_REGEXP_OPTIM
void QRegExpEngine::Box::setupHeuristics()
{
    eng->setupGoodStringHeuristic( earlyStart, lateStart, str );

    /*
      A regular expression such as 112|1 has occ1['2'] = 2 and minl =
      1 at this point. An entry of occ1 has to be at most minl or
      infinity for the rest of the algorithm to go well.

      We waited until here before normalizing these cases (instead of
      doing it in Box::orx()) because sometimes things improve by
      themselves. Consider for example (112|1)34.
    */
    for ( int i = 0; i < NumBadChars; i++ ) {
        if ( occ1[i] != NoOccurrence && occ1[i] >= minl )
            occ1[i] = minl;
    }
    eng->setupBadCharHeuristic( minl, occ1 );

    eng->heuristicallyChooseHeuristic();
}
#endif

#if defined(QT_DEBUG)
void QRegExpEngine::Box::dump() const
{
    int i;
    qDebug( "Box of at least %d character%s", minl, minl == 1 ? "" : "s" );
    qDebug( "  Left states:" );
    for ( i = 0; i < (int) ls.size(); i++ ) {
        if ( at(lanchors, ls[i]) == 0 )
            qDebug( "    %d", ls[i] );
        else
            qDebug( "    %d [anchors 0x%.8x]", ls[i], lanchors[ls[i]] );
    }
    qDebug( "  Right states:" );
    for ( i = 0; i < (int) rs.size(); i++ ) {
        if ( at(ranchors, rs[i]) == 0 )
            qDebug( "    %d", rs[i] );
        else
            qDebug( "    %d [anchors 0x%.8x]", rs[i], ranchors[rs[i]] );
    }
    qDebug( "  Skip anchors: 0x%.8x", skipanchors );
}
#endif

void QRegExpEngine::Box::addAnchorsToEngine( const Box& to ) const
{
    for ( int i = 0; i < (int) to.ls.size(); i++ ) {
        for ( int j = 0; j < (int) rs.size(); j++ ) {
            int a = eng->anchorConcatenation( at(ranchors, rs[j]),
                                              at(to.lanchors, to.ls[i]) );
            eng->addAnchors( rs[j], to.ls[i], a );
        }
    }
}

int QRegExpEngine::getChar()
{
    return ( yyPos == yyLen ) ? EOS : yyIn[yyPos++].unicode();
}

int QRegExpEngine::getEscape()
{
#ifndef QT_NO_REGEXP_ESCAPE
    const char tab[] = "afnrtv"; // no b, as \b means word boundary
    const char backTab[] = "\a\f\n\r\t\v";
    ushort low;
    int i;
#endif
    ushort val;
    int prevCh = yyCh;

    if ( prevCh == EOS ) {
        error( RXERR_END );
        return Tok_Char | '\\';
    }
    yyCh = getChar();
#ifndef QT_NO_REGEXP_ESCAPE
    if ( (prevCh & ~0xff) == 0 ) {
        const char *p = strchr( tab, prevCh );
        if ( p != 0 )
            return Tok_Char | backTab[p - tab];
    }
#endif

    switch ( prevCh ) {
#ifndef QT_NO_REGEXP_ESCAPE
    case '0':
        val = 0;
        for ( i = 0; i < 3; i++ ) {
            if ( yyCh >= '0' && yyCh <= '7' )
                val = ( val << 3 ) | ( yyCh - '0' );
            else
                break;
            yyCh = getChar();
        }
        if ( (val & ~0377) != 0 )
            error( RXERR_OCTAL );
        return Tok_Char | val;
#endif
#ifndef QT_NO_REGEXP_ESCAPE
    case 'B':
        return Tok_NonWord;
#endif
#ifndef QT_NO_REGEXP_CCLASS
    case 'D':
        // see QChar::isDigit()
        yyCharClass->addCategories( 0x7fffffef );
        return Tok_CharClass;
    case 'S':
        // see QChar::isSpace()
        yyCharClass->addCategories( 0x7ffff87f );
        yyCharClass->addRange( 0x0000, 0x0008 );
        yyCharClass->addRange( 0x000e, 0x001f );
        yyCharClass->addRange( 0x007f, 0x009f );
        return Tok_CharClass;
    case 'W':
        // see QChar::isLetterOrNumber()
        yyCharClass->addCategories( 0x7fe07f8f );
        yyCharClass->addRange( 0x203f, 0x2040 );
        yyCharClass->addSingleton( 0x2040 );
        yyCharClass->addSingleton( 0x30fb );
        yyCharClass->addRange( 0xfe33, 0xfe34 );
        yyCharClass->addRange( 0xfe4d, 0xfe4f );
        yyCharClass->addSingleton( 0xff3f );
        yyCharClass->addSingleton( 0xff65 );
        return Tok_CharClass;
#endif
#ifndef QT_NO_REGEXP_ESCAPE
    case 'b':
        return Tok_Word;
#endif
#ifndef QT_NO_REGEXP_CCLASS
    case 'd':
        // see QChar::isDigit()
        yyCharClass->addCategories( 0x00000010 );
        return Tok_CharClass;
    case 's':
        // see QChar::isSpace()
        yyCharClass->addCategories( 0x00000380 );
        yyCharClass->addRange( 0x0009, 0x000d );
        return Tok_CharClass;
    case 'w':
        // see QChar::isLetterOrNumber()
        yyCharClass->addCategories( 0x000f8070 );
        yyCharClass->addSingleton( 0x005f ); // '_'
        return Tok_CharClass;
#endif
#ifndef QT_NO_REGEXP_ESCAPE
    case 'x':
        val = 0;
        for ( i = 0; i < 4; i++ ) {
            low = QChar( yyCh ).lower();
            if ( low >= '0' && low <= '9' )
                val = ( val << 4 ) | ( low - '0' );
            else if ( low >= 'a' && low <= 'f' )
                val = ( val << 4 ) | ( low - 'a' + 10 );
            else
                break;
            yyCh = getChar();
        }
        return Tok_Char | val;
#endif
    default:
        if ( prevCh >= '1' && prevCh <= '9' ) {
#ifndef QT_NO_REGEXP_BACKREF
            val = prevCh - '0';
            while ( yyCh >= '0' && yyCh <= '9' ) {
                val = ( val *= 10 ) | ( yyCh - '0' );
                yyCh = getChar();
            }
            return Tok_BackRef | val;
#else
            error( RXERR_DISABLED );
#endif
        }
        return Tok_Char | prevCh;
    }
}

#ifndef QT_NO_REGEXP_INTERVAL
int QRegExpEngine::getRep( int def )
{
    if ( yyCh >= '0' && yyCh <= '9' ) {
        int rep = 0;
        do {
            rep = 10 * rep + yyCh - '0';
            if ( rep >= InftyRep ) {
                error( RXERR_REPETITION );
                rep = def;
            }
            yyCh = getChar();
        } while ( yyCh >= '0' && yyCh <= '9' );
        return rep;
    } else {
        return def;
    }
}
#endif

#ifndef QT_NO_REGEXP_LOOKAHEAD
void QRegExpEngine::skipChars( int n )
{
    if ( n > 0 ) {
        yyPos += n - 1;
        yyCh = getChar();
    }
}
#endif

void QRegExpEngine::error( const char *msg )
{
    if ( yyError.isEmpty() )
        yyError = QString::fromLatin1( msg );
}

void QRegExpEngine::startTokenizer( const QChar *rx, int len )
{
    yyIn = rx;
    yyPos0 = 0;
    yyPos = 0;
    yyLen = len;
    yyCh = getChar();
    yyCharClass = new CharClass;
    yyMinRep = 0;
    yyMaxRep = 0;
    yyError = QString();
}

int QRegExpEngine::getToken()
{
#ifndef QT_NO_REGEXP_CCLASS
    ushort pendingCh = 0;
    bool charPending;
    bool rangePending;
    int tok;
#endif
    int prevCh = yyCh;

    yyPos0 = yyPos - 1;
#ifndef QT_NO_REGEXP_CCLASS
    yyCharClass->clear();
#endif
    yyMinRep = 0;
    yyMaxRep = 0;
    yyCh = getChar();
    switch ( prevCh ) {
    case EOS:
        yyPos0 = yyPos;
        return Tok_Eos;
    case '$':
        return Tok_Dollar;
    case '(':
        if ( yyCh == '?' ) {
            prevCh = getChar();
            yyCh = getChar();
            switch ( prevCh ) {
#ifndef QT_NO_REGEXP_LOOKAHEAD
            case '!':
                return Tok_NegLookahead;
            case '=':
                return Tok_PosLookahead;
#endif
            case ':':
                return Tok_MagicLeftParen;
            default:
                error( RXERR_LOOKAHEAD );
                return Tok_MagicLeftParen;
            }
        } else {
            return Tok_LeftParen;
        }
    case ')':
        return Tok_RightParen;
    case '*':
        yyMinRep = 0;
        yyMaxRep = InftyRep;
        return Tok_Quantifier;
    case '+':
        yyMinRep = 1;
        yyMaxRep = InftyRep;
        return Tok_Quantifier;
    case '.':
#ifndef QT_NO_REGEXP_CCLASS
        yyCharClass->setNegative( TRUE );
#endif
        return Tok_CharClass;
    case '?':
        yyMinRep = 0;
        yyMaxRep = 1;
        return Tok_Quantifier;
    case '[':
#ifndef QT_NO_REGEXP_CCLASS
        if ( yyCh == '^' ) {
            yyCharClass->setNegative( TRUE );
            yyCh = getChar();
        }
        charPending = FALSE;
        rangePending = FALSE;
        do {
            if ( yyCh == '-' && charPending && !rangePending ) {
                rangePending = TRUE;
                yyCh = getChar();
            } else {
                if ( charPending && !rangePending ) {
                    yyCharClass->addSingleton( pendingCh );
                    charPending = FALSE;
                }
                if ( yyCh == '\\' ) {
                    yyCh = getChar();
                    tok = getEscape();
                    if ( tok == Tok_Word )
                        tok = '\b';
                } else {
                    tok = Tok_Char | yyCh;
                    yyCh = getChar();
                }
                if ( tok == Tok_CharClass ) {
                    if ( rangePending ) {
                        yyCharClass->addSingleton( '-' );
                        yyCharClass->addSingleton( pendingCh );
                        charPending = FALSE;
                        rangePending = FALSE;
                    }
                } else if ( (tok & Tok_Char) != 0 ) {
                    if ( rangePending ) {
                        yyCharClass->addRange( pendingCh, tok ^ Tok_Char );
                        charPending = FALSE;
                        rangePending = FALSE;
                    } else {
                        pendingCh = tok ^ Tok_Char;
                        charPending = TRUE;
                    }
                } else {
                    error( RXERR_CHARCLASS );
                }
            }
        }  while ( yyCh != ']' && yyCh != EOS );
        if ( rangePending )
            yyCharClass->addSingleton( '-' );
        if ( charPending )
            yyCharClass->addSingleton( pendingCh );
        if ( yyCh == EOS )
            error( RXERR_END );
        else
            yyCh = getChar();
        return Tok_CharClass;
#else
        error( RXERR_END );
        return Tok_Char | '[';
#endif
    case '\\':
        return getEscape();
    case ']':
        error( RXERR_LEFTDELIM );
        return Tok_Char | ']';
    case '^':
        return Tok_Caret;
    case '{':
#ifndef QT_NO_REGEXP_INTERVAL
        yyMinRep = getRep( 0 );
        yyMaxRep = yyMinRep;
        if ( yyCh == ',' ) {
            yyCh = getChar();
            yyMaxRep = getRep( InftyRep );
        }
        if ( yyMaxRep < yyMinRep )
            qSwap( yyMinRep, yyMaxRep );
        if ( yyCh != '}' )
            error( RXERR_REPETITION );
        yyCh = getChar();
        return Tok_Quantifier;
#else
        error( RXERR_DISABLED );
        return Tok_Char | '{';
#endif
    case '|':
        return Tok_Bar;
    case '}':
        error( RXERR_LEFTDELIM );
        return Tok_Char | '}';
    default:
        return Tok_Char | prevCh;
    }
}

int QRegExpEngine::parse( const QChar *pattern, int len )
{
    valid = TRUE;
    startTokenizer( pattern, len );
    yyTok = getToken();
#ifndef QT_NO_REGEXP_CAPTURE
    yyMayCapture = TRUE;
#else
    yyMayCapture = FALSE;
#endif

#ifndef QT_NO_REGEXP_CAPTURE
    int atom = startAtom( FALSE );
#endif
    CharClass anything;
    Box box( this ); // create InitialState
    box.set( anything );
    Box rightBox( this ); // create FinalState
    rightBox.set( anything );

    Box middleBox( this );
    parseExpression( &middleBox );
#ifndef QT_NO_REGEXP_CAPTURE
    finishAtom( atom );
#endif
#ifndef QT_NO_REGEXP_OPTIM
    middleBox.setupHeuristics();
#endif
    box.cat( middleBox );
    box.cat( rightBox );
    delete yyCharClass;
    yyCharClass = 0;

    officialncap = ncap;
#ifndef QT_NO_REGEXP_BACKREF
    if ( nbrefs > ncap )
        ncap = nbrefs;
#endif

    mmCaptured.resize( 2 + 2 * officialncap );
    mmCapturedNoMatch.fill( -1, 2 + 2 * officialncap );

    /*
      We use one QMemArray<int> for all the big data used a lot in
      matchHere() and friends.
    */
#ifndef QT_NO_REGEXP_OPTIM
    mmSlideTabSize = QMAX( minl + 1, 16 );
#else
    mmSlideTabSize = 0;
#endif
    mmBigArray.resize( (3 + 4 * ncap) * ns + 4 * ncap + mmSlideTabSize );

    mmInNextStack = mmBigArray.data();
    memset( mmInNextStack, -1, ns * sizeof(int) );
    mmCurStack = mmInNextStack + ns;
    mmNextStack = mmInNextStack + 2 * ns;

    mmCurCapBegin = mmInNextStack + 3 * ns;
    mmNextCapBegin = mmCurCapBegin + ncap * ns;
    mmCurCapEnd = mmCurCapBegin + 2 * ncap * ns;
    mmNextCapEnd = mmCurCapBegin + 3 * ncap * ns;

    mmTempCapBegin = mmCurCapBegin + 4 * ncap * ns;
    mmTempCapEnd = mmTempCapBegin + ncap;
    mmCapBegin = mmTempCapBegin + 2 * ncap;
    mmCapEnd = mmTempCapBegin + 3 * ncap;

    mmSlideTab = mmTempCapBegin + 4 * ncap;

    if ( !yyError.isEmpty() )
        return -1;

#ifndef QT_NO_REGEXP_OPTIM
    State *sinit = s[InitialState];
    caretAnchored = ( sinit->anchors != 0 );
    if ( caretAnchored ) {
        QMap<int, int>& anchors = *sinit->anchors;
        QMap<int, int>::ConstIterator a;
        for ( a = anchors.begin(); a != anchors.end(); ++a ) {
#ifndef QT_NO_REGEXP_ANCHOR_ALT
            if ( (*a & Anchor_Alternation) != 0 )
                break;
#endif
            if ( (*a & Anchor_Caret) == 0 ) {
                caretAnchored = FALSE;
                break;
            }
        }
    }
#endif
    return yyPos0;
}

void QRegExpEngine::parseAtom( Box *box )
{
#ifndef QT_NO_REGEXP_LOOKAHEAD
    QRegExpEngine *eng = 0;
    bool neg;
    int len;
#endif

    switch ( yyTok ) {
    case Tok_Dollar:
        box->catAnchor( Anchor_Dollar );
        break;
    case Tok_Caret:
        box->catAnchor( Anchor_Caret );
        break;
#ifndef QT_NO_REGEXP_LOOKAHEAD
    case Tok_PosLookahead:
    case Tok_NegLookahead:
        neg = ( yyTok == Tok_NegLookahead );
        eng = new QRegExpEngine( cs );
        len = eng->parse( yyIn + yyPos - 1, yyLen - yyPos + 1 );
        if ( len >= 0 )
            skipChars( len );
        else
            error( RXERR_LOOKAHEAD );
        box->catAnchor( addLookahead(eng, neg) );
        yyTok = getToken();
        if ( yyTok != Tok_RightParen )
            error( RXERR_LOOKAHEAD );
        break;
#endif
#ifndef QT_NO_REGEXP_ESCAPE
    case Tok_Word:
        box->catAnchor( Anchor_Word );
        break;
    case Tok_NonWord:
        box->catAnchor( Anchor_NonWord );
        break;
#endif
    case Tok_LeftParen:
    case Tok_MagicLeftParen:
        yyTok = getToken();
        parseExpression( box );
        if ( yyTok != Tok_RightParen )
            error( RXERR_END );
        break;
    case Tok_CharClass:
        box->set( *yyCharClass );
        break;
    case Tok_Quantifier:
        error( RXERR_REPETITION );
        break;
    default:
        if ( (yyTok & Tok_Char) != 0 )
            box->set( QChar(yyTok ^ Tok_Char) );
#ifndef QT_NO_REGEXP_BACKREF
        else if ( (yyTok & Tok_BackRef) != 0 )
            box->set( yyTok ^ Tok_BackRef );
#endif
        else
            error( RXERR_DISABLED );
    }
    yyTok = getToken();
}

void QRegExpEngine::parseFactor( Box *box )
{
#ifndef QT_NO_REGEXP_CAPTURE
    int atom = startAtom( yyMayCapture && yyTok == Tok_LeftParen );
#else
    static const int atom = 0;
#endif

#ifndef QT_NO_REGEXP_INTERVAL
#define YYREDO() \
        yyIn = in, yyPos0 = pos0, yyPos = pos, yyLen = len, yyCh = ch, \
        *yyCharClass = charClass, yyMinRep = 0, yyMaxRep = 0, yyTok = tok

    const QChar *in = yyIn;
    int pos0 = yyPos0;
    int pos = yyPos;
    int len = yyLen;
    int ch = yyCh;
    CharClass charClass;
    if ( yyTok == Tok_CharClass )
        charClass = *yyCharClass;
    int tok = yyTok;
    bool mayCapture = yyMayCapture;
#endif

    parseAtom( box );
#ifndef QT_NO_REGEXP_CAPTURE
    finishAtom( atom );
#endif

    if ( yyTok == Tok_Quantifier ) {
        if ( yyMaxRep == InftyRep ) {
            box->plus( atom );
#ifndef QT_NO_REGEXP_INTERVAL
        } else if ( yyMaxRep == 0 ) {
            box->clear();
#endif
        }
        if ( yyMinRep == 0 )
            box->opt();

#ifndef QT_NO_REGEXP_INTERVAL
        yyMayCapture = FALSE;
        int alpha = ( yyMinRep == 0 ) ? 0 : yyMinRep - 1;
        int beta = ( yyMaxRep == InftyRep ) ? 0 : yyMaxRep - ( alpha + 1 );

        Box rightBox( this );
        int i;

        for ( i = 0; i < beta; i++ ) {
            YYREDO();
            Box leftBox( this );
            parseAtom( &leftBox );
            leftBox.cat( rightBox );
            leftBox.opt();
            rightBox = leftBox;
        }
        for ( i = 0; i < alpha; i++ ) {
            YYREDO();
            Box leftBox( this );
            parseAtom( &leftBox );
            leftBox.cat( rightBox );
            rightBox = leftBox;
        }
        rightBox.cat( *box );
        *box = rightBox;
#endif
        yyTok = getToken();
#ifndef QT_NO_REGEXP_INTERVAL
        yyMayCapture = mayCapture;
#endif
    }
#undef YYREDO
}

void QRegExpEngine::parseTerm( Box *box )
{
#ifndef QT_NO_REGEXP_OPTIM
    if ( yyTok != Tok_Eos && yyTok != Tok_RightParen && yyTok != Tok_Bar )
        parseFactor( box );
#endif
    while ( yyTok != Tok_Eos && yyTok != Tok_RightParen && yyTok != Tok_Bar ) {
        Box rightBox( this );
        parseFactor( &rightBox );
        box->cat( rightBox );
    }
}

void QRegExpEngine::parseExpression( Box *box )
{
    parseTerm( box );
    while ( yyTok == Tok_Bar ) {
        Box rightBox( this );
        yyTok = getToken();
        parseTerm( &rightBox );
        box->orx( rightBox );
    }
}

/*
  The struct QRegExpPrivate contains the private data of a regular
  expression other than the automaton. It makes it possible for many
  QRegExp objects to use the same QRegExpEngine object with different
  QRegExpPrivate objects.
*/
struct QRegExpPrivate
{
    QString pattern; // regular-expression or wildcard pattern
    QString rxpattern; // regular-expression pattern
#ifndef QT_NO_REGEXP_WILDCARD
    bool wc; // wildcard mode?
#endif
    bool min; // minimal matching? (instead of maximal)
#ifndef QT_NO_REGEXP_CAPTURE
    QString t; // last string passed to QRegExp::search() or searchRev()
    QStringList capturedCache; // what QRegExp::capturedTexts() returned last
#endif
    QMemArray<int> captured; // what QRegExpEngine::search() returned last

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

#ifndef QT_NO_REGEXP_OPTIM
static QCache<QRegExpEngine> *engineCache = 0;
static QSingleCleanupHandler<QCache<QRegExpEngine> > cleanup_cache;
#endif

static QRegExpEngine *newEngine( const QString& pattern, bool caseSensitive )
{
#ifndef QT_NO_REGEXP_OPTIM
    if ( engineCache != 0 ) {
#ifdef QT_THREAD_SUPPORT
        QMutexLocker locker( qt_global_mutexpool ?
                             qt_global_mutexpool->get( &engineCache ) : 0 );
#endif
        QRegExpEngine *eng = engineCache->take( pattern );
        if ( eng == 0 || eng->caseSensitive() != caseSensitive ) {
            delete eng;
        } else {
            eng->ref();
            return eng;
        }
    }
#endif
    return new QRegExpEngine( pattern, caseSensitive );
}

static void derefEngine( QRegExpEngine *eng, const QString& pattern )
{
#ifdef QT_THREAD_SUPPORT
    QMutexLocker locker( qt_global_mutexpool ?
                         qt_global_mutexpool->get( &engineCache ) : 0 );
#endif
    if ( eng != 0 && eng->deref() ) {
#ifndef QT_NO_REGEXP_OPTIM
        if ( engineCache == 0 ) {
            engineCache = new QCache<QRegExpEngine>;
            engineCache->setAutoDelete( TRUE );
            cleanup_cache.set( &engineCache );
        }
        if ( !pattern.isNull() &&
             engineCache->insert(pattern, eng, 4 + pattern.length() / 4) )
            return;
#else
        Q_UNUSED( pattern );
#endif
        delete eng;
    }
}

QRegExp::QRegExp()
{
    eng = new QRegExpEngine( TRUE );
    priv = new QRegExpPrivate;
#ifndef QT_NO_REGEXP_WILDCARD
    priv->wc = FALSE;
#endif
    priv->min = FALSE;
    compile( TRUE );
}

QRegExp::QRegExp( const QString& pattern, bool caseSensitive, bool wildcard )
{
    eng = 0;
    priv = new QRegExpPrivate;
    priv->pattern = pattern;
#ifndef QT_NO_REGEXP_WILDCARD
    priv->wc = wildcard;
#endif
    priv->min = FALSE;
    compile( caseSensitive );
}

QRegExp::QRegExp( const QRegExp& rx )
{
    eng = 0;
    priv = new QRegExpPrivate;
    operator=( rx );
}

QRegExp::~QRegExp()
{
    derefEngine( eng, priv->rxpattern );
    delete priv;
}

QRegExp& QRegExp::operator=( const QRegExp& rx )
{
    rx.eng->ref();
    derefEngine( eng, priv->rxpattern );
    eng = rx.eng;
    priv->pattern = rx.priv->pattern;
    priv->rxpattern = rx.priv->rxpattern;
#ifndef QT_NO_REGEXP_WILDCARD
    priv->wc = rx.priv->wc;
#endif
    priv->min = rx.priv->min;
#ifndef QT_NO_REGEXP_CAPTURE
    priv->t = rx.priv->t;
    priv->capturedCache = rx.priv->capturedCache;
#endif
    priv->captured = rx.priv->captured;
    return *this;
}

bool QRegExp::operator==( const QRegExp& rx ) const
{
    return priv->pattern == rx.priv->pattern &&
           eng->caseSensitive() == rx.eng->caseSensitive() &&
#ifndef QT_NO_REGEXP_WILDCARD
           priv->wc == rx.priv->wc &&
#endif
           priv->min == rx.priv->min;
}

bool QRegExp::isEmpty() const
{
    return priv->pattern.isEmpty();
}

bool QRegExp::isValid() const
{
    return eng->isValid();
}

QString QRegExp::pattern() const
{
    return priv->pattern;
}

void QRegExp::setPattern( const QString& pattern )
{
    if ( priv->pattern != pattern ) {
        priv->pattern = pattern;
        compile( caseSensitive() );
    }
}

bool QRegExp::caseSensitive() const
{
    return eng->caseSensitive();
}

void QRegExp::setCaseSensitive( bool sensitive )
{
    if ( sensitive != eng->caseSensitive() )
        compile( sensitive );
}

#ifndef QT_NO_REGEXP_WILDCARD

bool QRegExp::wildcard() const
{
    return priv->wc;
}

void QRegExp::setWildcard( bool wildcard )
{
    if ( wildcard != priv->wc ) {
        priv->wc = wildcard;
        compile( caseSensitive() );
    }
}
#endif

bool QRegExp::minimal() const
{
    return priv->min;
}

void QRegExp::setMinimal( bool minimal )
{
    priv->min = minimal;
}

bool QRegExp::exactMatch( const QString& str ) const
{
#ifndef QT_NO_REGEXP_CAPTURE
    priv->t = str;
    priv->capturedCache.clear();
#endif

    priv->captured = eng->match( str, 0, priv->min, TRUE, 0 );
    if ( priv->captured[1] == (int) str.length() ) {
        return TRUE;
    } else {
        priv->captured.detach();
        priv->captured[0] = 0;
        priv->captured[1] = eng->matchedLength();
        return FALSE;
    }
}

#ifndef QT_NO_COMPAT

int QRegExp::match( const QString& str, int index, int *len,
                    bool indexIsStart ) const
{
    int pos = search( str, index, indexIsStart ? CaretAtOffset : CaretAtZero );
    if ( len != 0 )
        *len = matchedLength();
    return pos;
}
#endif // QT_NO_COMPAT

int QRegExp::search( const QString& str, int offset ) const
{
    return search( str, offset, CaretAtZero );
}

int QRegExp::search( const QString& str, int offset, CaretMode caretMode ) const
{
    if ( offset < 0 )
        offset += str.length();
#ifndef QT_NO_REGEXP_CAPTURE
    priv->t = str;
    priv->capturedCache.clear();
#endif
    priv->captured = eng->match( str, offset, priv->min, FALSE,
                                 caretIndex(offset, caretMode) );
    return priv->captured[0];
}


int QRegExp::searchRev( const QString& str, int offset ) const
{
    return searchRev( str, offset, CaretAtZero );
}

int QRegExp::searchRev( const QString& str, int offset,
                        CaretMode caretMode ) const
{
    if ( offset < 0 )
        offset += str.length();
#ifndef QT_NO_REGEXP_CAPTURE
    priv->t = str;
    priv->capturedCache.clear();
#endif
    if ( offset < 0 || offset > (int) str.length() ) {
        priv->captured.detach();
        priv->captured.fill( -1 );
        return -1;
    }

    while ( offset >= 0 ) {
        priv->captured = eng->match( str, offset, priv->min, TRUE,
                                     caretIndex(offset, caretMode) );
        if ( priv->captured[0] == offset )
            return offset;
        offset--;
    }
    return -1;
}

int QRegExp::matchedLength() const
{
    return priv->captured[1];
}

#ifndef QT_NO_REGEXP_CAPTURE

int QRegExp::numCaptures() const
{
    return eng->numCaptures();
}



QStringList QRegExp::capturedTexts()
{
    if ( priv->capturedCache.isEmpty() ) {
        for ( int i = 0; i < (int) priv->captured.size(); i += 2 ) {
            QString m;
            if ( priv->captured[i + 1] == 0 )
                m = QString::fromLatin1( "" );
            else if ( priv->captured[i] >= 0 )
                m = priv->t.mid( priv->captured[i],
                                 priv->captured[i + 1] );
            priv->capturedCache.append( m );
        }
        priv->t = QString::null;
    }
    return priv->capturedCache;
}

QString QRegExp::cap( int nth )
{
    if ( nth < 0 || nth >= (int) priv->captured.size() / 2 )
        return QString::null;
    else
        return capturedTexts()[nth];
}

int QRegExp::pos( int nth )
{
    if ( nth < 0 || nth >= (int) priv->captured.size() / 2 )
        return -1;
    else
        return priv->captured[2 * nth];
}

QString QRegExp::errorString()
{
    if ( isValid() ) {
        return QString( RXERR_OK );
    } else {
        return eng->errorString();
    }
}
#endif

QString QRegExp::escape( const QString& str )
{
    static const char meta[] = "$()*+.?[\\]^{|}";
    QString quoted = str;
    int i = 0;

    while ( i < (int) quoted.length() ) {
        if ( strchr(meta, quoted[i].latin1()) != 0 )
            quoted.insert( i++, "\\" );
        i++;
    }
    return quoted;
}

void QRegExp::compile( bool caseSensitive )
{
    derefEngine( eng, priv->rxpattern );
#ifndef QT_NO_REGEXP_WILDCARD
    if ( priv->wc )
        priv->rxpattern = wc2rx( priv->pattern );
    else
#endif
        priv->rxpattern = priv->pattern.isNull() ? QString::fromLatin1( "" )
                          : priv->pattern;
    eng = newEngine( priv->rxpattern, caseSensitive );
#ifndef QT_NO_REGEXP_CAPTURE
    priv->t = QString();
    priv->capturedCache.clear();
#endif
    priv->captured.detach();
    priv->captured.fill( -1, 2 + 2 * eng->numCaptures() );
}

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

#endif // QT_NO_REGEXP

---