qregexparser.h - mozsearch

++ // Copyright (C) 2017-2020 Ford Motor Company.

++ // Copyright (C) 2017 The Qt Company Ltd.

++ // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only

++ // Qt-Security score:significant reason:parsing-build-time-only

++

++ #ifndef QREGEXPARSER_H

++ #define QREGEXPARSER_H

++

++ #include <QtCore/qshareddata.h>

++ #include <QtCore/qvarlengtharray.h>

++ #include <QtCore/qvariant.h>

++ #include <QtCore/qregularexpression.h>

++ #include <QtCore/qmap.h>

++ #include <QtCore/qfile.h>

++ #include <QtCore/qtextstream.h>

++ #include <QtCore/qdebug.h>

++

++ QT_BEGIN_NAMESPACE

++

++ struct MatchCandidate {

++     MatchCandidate(const QString &n, const QString &t, int i) : name(n), matchText(t), index(i) {}

++     QString name;

++     QString matchText;

++     int index;

++ };

++

++ template <typename _Parser, typename _Table>

++ class QRegexParser: protected _Table

++ {

++ public:

++     QRegexParser(int maxMatchLen=4096);

++     virtual ~QRegexParser();

++

++     virtual bool parse();

++

++     virtual void reset() {}

++

++     inline QVariant &sym(int index);

++

++     void setBuffer(const QString &buffer);

++

++     void setBufferFromDevice(QIODevice *device);

++

++     void setDebug();

++

++     QString errorString() const

++     {

++         return m_errorString;

++     }

++

++     void setErrorString(const QString &error)

++     {

++         m_errorString = error;

++         qWarning() << m_errorString;

++     }

++

++     inline const QMap<QString, QString>& captured() const

++     {

++         return m_captured;

++     }

++

++     inline bool isDebug() const

++     {

++         return m_debug;

++     }

++

++     inline int lineNumber() const

++     {

++         return m_lineno;

++     }

++

++ private:

++     int nextToken();

++

++     inline bool consumeRule(int rule)

++     {

++         return static_cast<_Parser*> (this)->consumeRule(rule);

++     }

++

++     enum { DefaultStackSize = 128 };

++

++     struct Data: public QSharedData

++     {

++         Data(): stackSize (DefaultStackSize), tos (0) {}

++

++         QVarLengthArray<int, DefaultStackSize> stateStack;

++         QVarLengthArray<QVariant, DefaultStackSize> parseStack;

++         int stackSize;

++         int tos;

++

++         void reallocateStack() {

++             stackSize <<= 1;

++             stateStack.resize(stackSize);

++             parseStack.resize(stackSize);

++         }

++     };

++

++     inline QString escapeString(QString s)

++     {

++         return s.replace(QLatin1Char('\n'), QLatin1String("\\n")).replace(QLatin1Char('\t'), QLatin1String("\\t"));

++     }

++

++     QSharedDataPointer<Data> d;

++

++     QList<QRegularExpression> m_regexes;

++     QMap<QChar, QList<int> > regexCandidates;

++     QList<int> m_tokens;

++     QString m_buffer, m_lastMatchText;

++     int m_loc, m_lastNewlinePosition;

++     int m_lineno;

++     int m_debug;

++     QStringList m_tokenNames;

++     QMap<QString, QString> m_captured;

++     int m_maxMatchLen;

++     QString m_errorString;

++     QList<QMap<int, QString>> m_names; //storage for match names

++ };

++

++ template <typename _Parser, typename _Table>

++ inline QVariant &QRegexParser<_Parser, _Table>::sym(int n)

++ {

++     return d->parseStack [d->tos + n - 1];

++ }

++

++ template <typename _Parser, typename _Table>

++ QRegexParser<_Parser, _Table>::~QRegexParser()

++ {

++ }

++

++ template <typename _Parser, typename _Table>

++ bool QRegexParser<_Parser, _Table>::parse()

++ {

++     m_errorString.clear();

++     reset();

++     const int INITIAL_STATE = 0;

++

++     d->tos = 0;

++     d->reallocateStack();

++

++     int act = d->stateStack[++d->tos] = INITIAL_STATE;

++     int token = -1;

++

++     Q_FOREVER {

++         if (token == -1 && - _Table::TERMINAL_COUNT != _Table::action_index[act])

++             token = nextToken();

++

++         act = _Table::t_action(act, token);

++

++         if (d->stateStack[d->tos] == _Table::ACCEPT_STATE)

++             return true;

++

++         else if (act > 0) {

++             if (++d->tos == d->stackSize)

++                 d->reallocateStack();

++

++             d->parseStack[d->tos] = d->parseStack[d->tos - 1];

++             d->stateStack[d->tos] = act;

++             token = -1;

++         }

++

++         else if (act < 0) {

++             int r = - act - 1;

++             d->tos -= _Table::rhs[r];

++             act = d->stateStack[d->tos++];

++             if (!consumeRule(r))

++                 return false;

++             act = d->stateStack[d->tos] = _Table::nt_action(act, _Table::lhs[r] - _Table::TERMINAL_COUNT);

++         }

++

++         else break;

++     }

++

++     setErrorString(QStringLiteral("Unknown token encountered"));

++     return false;

++ }

++

++ template <typename _Parser, typename _Table>

++ QRegexParser<_Parser, _Table>::QRegexParser(int maxMatchLen) : d(new Data()), m_loc(0), m_lastNewlinePosition(0), m_lineno(1), m_debug(0), m_maxMatchLen(maxMatchLen)

++ {

++     QRegularExpression re(QStringLiteral("\\[([_a-zA-Z][_0-9a-zA-Z]*)(,\\s*M)?\\](.+)$"));

++     re.optimize();

++     QMap<QString, int> token_lookup;

++     QMap<int, QString> names;

++     for (int i = 1; i < _Table::lhs[0]; i++) {

++         const QString text = QLatin1String(_Table::spell[i]);

++         names.clear();

++         QRegularExpressionMatch match = re.match(text, 0, QRegularExpression::NormalMatch, QRegularExpression::DontCheckSubjectStringMatchOption);

++         if (match.hasMatch()) {

++             const QString token = match.captured(1);

++             const bool multiline = match.captured(2).size() > 0;

++             const QString pattern = match.captured(3);

++             m_tokenNames.append(token);

++             int index = i;

++             if (token_lookup.contains(token))

++                 index = token_lookup[token];

++             else

++                 token_lookup[token] = i;

++             QRegularExpression pat(pattern);

++             if (multiline)

++                 pat.setPatternOptions(QRegularExpression::DotMatchesEverythingOption);

++

++             if (!pat.isValid())

++                 qCritical() << "Pattern error for token #" << i << "for" << text << "pattern =" << pat << ":" << pat.errorString();

++             else {

++                 pat.optimize();

++                 int counter = 0;

++                 const auto namedCaptureGroups = pat.namedCaptureGroups();

++                 for (const QString &name : namedCaptureGroups) {

++                     if (!name.isEmpty())

++                         names.insert(counter, name);

++                     ++counter;

++                 }

++                 m_names.append(names);

++                 m_regexes.append(pat);

++                 if (token.startsWith(QLatin1String("ignore")))

++                     m_tokens.append(-1);

++                 else

++                     m_tokens.append(index);

++             }

++         } else {

++             qCritical() << "Error parsing regex at token #" << i << "for" << text << "Invalid syntax";

++         }

++     }

++ }

++

++ template <typename _Parser, typename _Table>

++ void QRegexParser<_Parser, _Table>::setBuffer(const QString &buffer)

++ {

++     m_buffer = buffer;

++ }

++

++ template <typename _Parser, typename _Table>

++ void QRegexParser<_Parser, _Table>::setBufferFromDevice(QIODevice *device)

++ {

++     QTextStream in(device);

++     m_buffer = in.readAll();

++ }

++

++ template <typename _Parser, typename _Table>

++ void QRegexParser<_Parser, _Table>::setDebug()

++ {

++     m_debug = true;

++     for (int r = 0; r < _Table::RULE_COUNT; ++r)

++     {

++         int ridx = _Table::rule_index[r];

++         int _rhs = _Table::rhs[r];

++         qDebug("%3d) %s ::=", r + 1, _Table::spell[_Table::rule_info[ridx]]);

++         ++ridx;

++         for (int i = ridx; i < ridx + _rhs; ++i)

++         {

++             int symbol = _Table::rule_info[i];

++             if (symbol > 0 && symbol < _Table::lhs[0])

++                 qDebug("     token_%s (pattern = %s)",qPrintable(m_tokenNames[symbol-1]),qPrintable(m_regexes[symbol-1].pattern()));

++             else if (const char *name = _Table::spell[symbol])

++                 qDebug("     %s", name);

++             else

++                 qDebug("     #%d", symbol);

++         }

++         qDebug();

++     }

++ }

++

++ template <typename _Parser, typename _Table>

++ int QRegexParser<_Parser, _Table>::nextToken()

++ {

++     const QStringView buffer { m_buffer };

++     static const QRegularExpression newline(QLatin1String("(\\n)"));

++     int token = -1;

++     while (token < 0)

++     {

++         if (m_loc == buffer.size())

++             return _Table::EOF_SYMBOL;

++

++         //Check m_lastMatchText for newlines and update m_lineno

++         //This isn't necessary, but being able to provide the line # and character #

++         //where the match is failing sure makes building/debugging grammars easier.

++         QRegularExpressionMatchIterator  matches = newline.globalMatch(m_lastMatchText);

++         while (matches.hasNext()) {

++             m_lineno++;

++             QRegularExpressionMatch match = matches.next();

++             if (!matches.hasNext())

++                 m_lastNewlinePosition += match.capturedEnd();

++         }

++

++         if (m_debug) {

++             qDebug();

++             qDebug() << "nextToken loop, line =" << m_lineno

++                 << "line position =" << m_loc - m_lastNewlinePosition

++                 << "next 5 characters =" << escapeString(buffer.mid(m_loc, 5).toString());

++         }

++         int best = -1, maxLen = -1;

++         QRegularExpressionMatch bestRegex;

++

++         //Find the longest match.

++         //If more than one are the same (longest) length, return the first one in

++         //the order defined.

++         QList<MatchCandidate> candidates;

++         //We used PCRE's PartialMatch to eliminate most of the regexes by the first

++         //character, so we keep a regexCandidates map with the list of possible regexes

++         //based on initial characters found so far.

++         const QChar nextChar = buffer.at(m_loc);

++         //Populate the list if we haven't seeen this character before

++         if (!regexCandidates.contains(nextChar)) {

++             const QStringView tmp = buffer.mid(m_loc,1);

++             int i = 0;

++             regexCandidates[nextChar] = QList<int>();

++             for (const QRegularExpression &re : std::as_const(m_regexes))

++             {

++                 QRegularExpressionMatch match = re.matchView(tmp, 0, QRegularExpression::PartialPreferFirstMatch, QRegularExpression::DontCheckSubjectStringMatchOption);

++                 //qDebug() << nextChar << tmp << match.hasMatch() << match.hasPartialMatch() << re.pattern();

++                 if (match.hasMatch() || match.hasPartialMatch())

++                     regexCandidates[nextChar] << i;

++                 i++;

++             }

++         }

++         const auto indices = regexCandidates.value(nextChar);

++         for (int i : indices)

++         {

++             //Seems like I should be able to run the regex on the entire string, but performance is horrible

++             //unless I use a substring.

++             //QRegularExpressionMatch match = m_regexes[i].match(m_buffer, m_loc, QRegularExpression::NormalMatch, QRegularExpression::AnchorAtOffsetMatchOption);

++             QRegularExpressionMatch match = m_regexes.at(i).matchView(buffer.mid(m_loc, m_maxMatchLen), 0, QRegularExpression::NormalMatch, QRegularExpression::AnchorAtOffsetMatchOption | QRegularExpression::DontCheckSubjectStringMatchOption);

++             if (match.hasMatch()) {

++                 if (m_debug)

++                     candidates << MatchCandidate(m_tokenNames[i], match.captured(), i);

++                 if (match.capturedLength() > maxLen) {

++                     best = i;

++                     maxLen = match.capturedLength();

++                     bestRegex = match;

++                 }

++             }

++         }

++         if (best < 0) {

++             setErrorString(QLatin1String("Error generating tokens from file, next characters >%1<").arg(buffer.mid(m_loc, 15)));

++             return -1;

++         } else {

++             const QMap<int, QString> &map = m_names.at(best);

++             if (!map.isEmpty())

++                 m_captured.clear();

++             for (auto iter = map.cbegin(), end = map.cend(); iter != end; ++iter)

++                 m_captured.insert(iter.value(), bestRegex.captured(iter.key()));

++             if (m_debug) {

++                 qDebug() << "Match candidates:";

++                 for (const MatchCandidate &m : std::as_const(candidates)) {

++                     QLatin1String result = m.index == best ? QLatin1String(" * ") : QLatin1String("   ");

++                     qDebug() << qPrintable(result) << qPrintable(m.name) << qPrintable(escapeString(m.matchText));

++                 }

++             }

++             m_loc += maxLen;

++             if (m_tokens.at(best) >= 0)

++                 token = m_tokens.at(best);

++             m_lastMatchText = bestRegex.captured(0);

++         }

++     }

++     return token;

++ }

++

++ QT_END_NAMESPACE

++

++ #endif // QREGEXPARSER_H

Revision control