summaryrefslogtreecommitdiffstats
path: root/kutils/kfind.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'kutils/kfind.cpp')
-rw-r--r--kutils/kfind.cpp710
1 files changed, 710 insertions, 0 deletions
diff --git a/kutils/kfind.cpp b/kutils/kfind.cpp
new file mode 100644
index 000000000..a6eb8dd46
--- /dev/null
+++ b/kutils/kfind.cpp
@@ -0,0 +1,710 @@
+/*
+ Copyright (C) 2001, S.R.Haque <srhaque@iee.org>.
+ Copyright (C) 2002, David Faure <david@mandrakesoft.com>
+ Copyright (C) 2004, Arend van Beelen jr. <arend@auton.nl>
+ This file is part of the KDE project
+
+ This library is free software; you can redistribute it and/or
+ modify it under the terms of the GNU Library General Public
+ License version 2, as published by the Free Software Foundation.
+
+ This library is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Library General Public License for more details.
+
+ You should have received a copy of the GNU Library General Public License
+ along with this library; see the file COPYING.LIB. If not, write to
+ the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ Boston, MA 02110-1301, USA.
+*/
+
+#include "kfind.h"
+#include "kfinddialog.h"
+#include <kapplication.h>
+#include <klocale.h>
+#include <kmessagebox.h>
+#include <qlabel.h>
+#include <qregexp.h>
+#include <qstylesheet.h>
+#include <qguardedptr.h>
+#include <qptrvector.h>
+#include <kdebug.h>
+
+//#define DEBUG_FIND
+
+#define INDEX_NOMATCH -1
+
+class KFindNextDialog : public KDialogBase
+{
+public:
+ KFindNextDialog(const QString &pattern, QWidget *parent);
+};
+
+// Create the dialog.
+KFindNextDialog::KFindNextDialog(const QString &pattern, QWidget *parent) :
+ KDialogBase(parent, 0, false, // non-modal!
+ i18n("Find Next"),
+ User1 | Close,
+ User1,
+ false,
+ KStdGuiItem::find())
+{
+ setMainWidget( new QLabel( i18n("<qt>Find next occurrence of '<b>%1</b>'?</qt>").arg(pattern), this ) );
+}
+
+////
+
+struct KFind::Private
+{
+ Private() :
+ findDialog(0),
+ patternChanged(false),
+ matchedPattern(""),
+ incrementalPath(29, true),
+ emptyMatch(0),
+ currentId(0),
+ customIds(false)
+ {
+ incrementalPath.setAutoDelete(true);
+ data.setAutoDelete(true);
+ }
+
+ ~Private()
+ {
+ delete emptyMatch;
+ emptyMatch = 0;
+ }
+
+ struct Match
+ {
+ Match(int dataId, int index, int matchedLength) :
+ dataId(dataId),
+ index(index),
+ matchedLength(matchedLength)
+ { }
+
+ int dataId;
+ int index;
+ int matchedLength;
+ };
+
+ struct Data
+ {
+ Data() : id(-1), dirty(false) { }
+ Data(int id, const QString &text, bool dirty = false) :
+ id(id),
+ text(text),
+ dirty(dirty)
+ { }
+
+ int id;
+ QString text;
+ bool dirty;
+ };
+
+ QGuardedPtr<QWidget> findDialog;
+ bool patternChanged;
+ QString matchedPattern;
+ QDict<Match> incrementalPath;
+ Match * emptyMatch;
+ QPtrVector<Data> data;
+ int currentId;
+ bool customIds;
+};
+
+////
+
+KFind::KFind( const QString &pattern, long options, QWidget *parent )
+ : QObject( parent )
+{
+ d = new KFind::Private;
+ m_options = options;
+ init( pattern );
+}
+
+KFind::KFind( const QString &pattern, long options, QWidget *parent, QWidget *findDialog )
+ : QObject( parent )
+{
+ d = new KFind::Private;
+ d->findDialog = findDialog;
+ m_options = options;
+ init( pattern );
+}
+
+void KFind::init( const QString& pattern )
+{
+ m_matches = 0;
+ m_pattern = pattern;
+ m_dialog = 0;
+ m_dialogClosed = false;
+ m_index = INDEX_NOMATCH;
+ m_lastResult = NoMatch;
+ if (m_options & KFindDialog::RegularExpression)
+ m_regExp = new QRegExp(pattern, m_options & KFindDialog::CaseSensitive);
+ else {
+ m_regExp = 0;
+ }
+}
+
+KFind::~KFind()
+{
+ delete m_dialog;
+ delete d;
+}
+
+bool KFind::needData() const
+{
+ // always true when m_text is empty.
+ if (m_options & KFindDialog::FindBackwards)
+ // m_index==-1 and m_lastResult==Match means we haven't answered nomatch yet
+ // This is important in the "replace with a prompt" case.
+ return ( m_index < 0 && m_lastResult != Match );
+ else
+ // "index over length" test removed: we want to get a nomatch before we set data again
+ // This is important in the "replace with a prompt" case.
+ return m_index == INDEX_NOMATCH;
+}
+
+void KFind::setData( const QString& data, int startPos )
+{
+ setData( -1, data, startPos );
+}
+
+void KFind::setData( int id, const QString& data, int startPos )
+{
+ // cache the data for incremental find
+ if ( m_options & KFindDialog::FindIncremental )
+ {
+ if ( id != -1 )
+ d->customIds = true;
+ else
+ id = d->currentId + 1;
+
+ if ( id >= (int) d->data.size() )
+ d->data.resize( id + 100 );
+
+ d->data.insert( id, new Private::Data(id, data, true) );
+ }
+
+ if ( !(m_options & KFindDialog::FindIncremental) || needData() )
+ {
+ m_text = data;
+
+ if ( startPos != -1 )
+ m_index = startPos;
+ else if (m_options & KFindDialog::FindBackwards)
+ m_index = m_text.length();
+ else
+ m_index = 0;
+#ifdef DEBUG_FIND
+ kdDebug() << "setData: '" << m_text << "' m_index=" << m_index << endl;
+#endif
+ Q_ASSERT( m_index != INDEX_NOMATCH );
+ m_lastResult = NoMatch;
+
+ d->currentId = id;
+ }
+}
+
+KDialogBase* KFind::findNextDialog( bool create )
+{
+ if ( !m_dialog && create )
+ {
+ m_dialog = new KFindNextDialog( m_pattern, parentWidget() );
+ connect( m_dialog, SIGNAL( user1Clicked() ), this, SLOT( slotFindNext() ) );
+ connect( m_dialog, SIGNAL( finished() ), this, SLOT( slotDialogClosed() ) );
+ }
+ return m_dialog;
+}
+
+KFind::Result KFind::find()
+{
+ Q_ASSERT( m_index != INDEX_NOMATCH || d->patternChanged );
+
+ if ( m_lastResult == Match && !d->patternChanged )
+ {
+ // Move on before looking for the next match, _if_ we just found a match
+ if (m_options & KFindDialog::FindBackwards) {
+ m_index--;
+ if ( m_index == -1 ) // don't call KFind::find with -1, it has a special meaning
+ {
+ m_lastResult = NoMatch;
+ return NoMatch;
+ }
+ } else
+ m_index++;
+ }
+ d->patternChanged = false;
+
+ if ( m_options & KFindDialog::FindIncremental )
+ {
+ // if the current pattern is shorter than the matchedPattern we can
+ // probably look up the match in the incrementalPath
+ if ( m_pattern.length() < d->matchedPattern.length() )
+ {
+ Private::Match *match = m_pattern.isEmpty() ? d->emptyMatch : d->incrementalPath[m_pattern];
+ QString previousPattern = d->matchedPattern;
+ d->matchedPattern = m_pattern;
+ if ( match != 0 )
+ {
+ bool clean = true;
+
+ // find the first result backwards on the path that isn't dirty
+ while ( d->data[match->dataId]->dirty == true &&
+ !m_pattern.isEmpty() )
+ {
+ m_pattern.truncate( m_pattern.length() - 1 );
+
+ match = d->incrementalPath[m_pattern];
+
+ clean = false;
+ }
+
+ // remove all matches that lie after the current match
+ while ( m_pattern.length() < previousPattern.length() )
+ {
+ d->incrementalPath.remove(previousPattern);
+ previousPattern.truncate(previousPattern.length() - 1);
+ }
+
+ // set the current text, index, etc. to the found match
+ m_text = d->data[match->dataId]->text;
+ m_index = match->index;
+ m_matchedLength = match->matchedLength;
+ d->currentId = match->dataId;
+
+ // if the result is clean we can return it now
+ if ( clean )
+ {
+ if ( d->customIds )
+ emit highlight(d->currentId, m_index, m_matchedLength);
+ else
+ emit highlight(m_text, m_index, m_matchedLength);
+
+ m_lastResult = Match;
+ d->matchedPattern = m_pattern;
+ return Match;
+ }
+ }
+ // if we couldn't look up the match, the new pattern isn't a
+ // substring of the matchedPattern, so we start a new search
+ else
+ {
+ startNewIncrementalSearch();
+ }
+ }
+ // if the new pattern is longer than the matchedPattern we might be
+ // able to proceed from the last search
+ else if ( m_pattern.length() > d->matchedPattern.length() )
+ {
+ // continue from the previous pattern
+ if ( m_pattern.startsWith(d->matchedPattern) )
+ {
+ // we can't proceed from the previous position if the previous
+ // position already failed
+ if ( m_index == INDEX_NOMATCH )
+ return NoMatch;
+
+ QString temp = m_pattern;
+ m_pattern.truncate(d->matchedPattern.length() + 1);
+ d->matchedPattern = temp;
+ }
+ // start a new search
+ else
+ {
+ startNewIncrementalSearch();
+ }
+ }
+ // if the new pattern is as long as the matchedPattern, we reset if
+ // they are not equal
+ else if ( m_pattern != d->matchedPattern )
+ {
+ startNewIncrementalSearch();
+ }
+ }
+
+#ifdef DEBUG_FIND
+ kdDebug() << k_funcinfo << "m_index=" << m_index << endl;
+#endif
+ do
+ {
+ // if we have multiple data blocks in our cache, walk through these
+ // blocks till we either searched all blocks or we find a match
+ do
+ {
+ // Find the next candidate match.
+ if ( m_options & KFindDialog::RegularExpression )
+ m_index = KFind::find(m_text, *m_regExp, m_index, m_options, &m_matchedLength);
+ else
+ m_index = KFind::find(m_text, m_pattern, m_index, m_options, &m_matchedLength);
+
+ if ( m_options & KFindDialog::FindIncremental )
+ d->data[d->currentId]->dirty = false;
+
+ if ( m_index == -1 && d->currentId < (int) d->data.count() - 1 )
+ {
+ m_text = d->data[++d->currentId]->text;
+
+ if ( m_options & KFindDialog::FindBackwards )
+ m_index = m_text.length();
+ else
+ m_index = 0;
+ }
+ else
+ break;
+ } while ( !(m_options & KFindDialog::RegularExpression) );
+
+ if ( m_index != -1 )
+ {
+ // Flexibility: the app can add more rules to validate a possible match
+ if ( validateMatch( m_text, m_index, m_matchedLength ) )
+ {
+ bool done = true;
+
+ if ( m_options & KFindDialog::FindIncremental )
+ {
+ if ( m_pattern.isEmpty() ) {
+ delete d->emptyMatch;
+ d->emptyMatch = new Private::Match( d->currentId, m_index, m_matchedLength );
+ } else
+ d->incrementalPath.replace(m_pattern, new Private::Match(d->currentId, m_index, m_matchedLength));
+
+ if ( m_pattern.length() < d->matchedPattern.length() )
+ {
+ m_pattern += d->matchedPattern.mid(m_pattern.length(), 1);
+ done = false;
+ }
+ }
+
+ if ( done )
+ {
+ m_matches++;
+ // Tell the world about the match we found, in case someone wants to
+ // highlight it.
+ if ( d->customIds )
+ emit highlight(d->currentId, m_index, m_matchedLength);
+ else
+ emit highlight(m_text, m_index, m_matchedLength);
+
+ if ( !m_dialogClosed )
+ findNextDialog(true)->show();
+
+#ifdef DEBUG_FIND
+ kdDebug() << k_funcinfo << "Match. Next m_index=" << m_index << endl;
+#endif
+ m_lastResult = Match;
+ return Match;
+ }
+ }
+ else // Skip match
+ {
+ if (m_options & KFindDialog::FindBackwards)
+ m_index--;
+ else
+ m_index++;
+ }
+ }
+ else
+ {
+ if ( m_options & KFindDialog::FindIncremental )
+ {
+ QString temp = m_pattern;
+ temp.truncate(temp.length() - 1);
+ m_pattern = d->matchedPattern;
+ d->matchedPattern = temp;
+ }
+
+ m_index = INDEX_NOMATCH;
+ }
+ }
+ while (m_index != INDEX_NOMATCH);
+
+#ifdef DEBUG_FIND
+ kdDebug() << k_funcinfo << "NoMatch. m_index=" << m_index << endl;
+#endif
+ m_lastResult = NoMatch;
+ return NoMatch;
+}
+
+void KFind::startNewIncrementalSearch()
+{
+ Private::Match *match = d->emptyMatch;
+ if(match == 0)
+ {
+ m_text = QString::null;
+ m_index = 0;
+ d->currentId = 0;
+ }
+ else
+ {
+ m_text = d->data[match->dataId]->text;
+ m_index = match->index;
+ d->currentId = match->dataId;
+ }
+ m_matchedLength = 0;
+ d->incrementalPath.clear();
+ delete d->emptyMatch;
+ d->emptyMatch = 0;
+ d->matchedPattern = m_pattern;
+ m_pattern = QString::null;
+}
+
+// static
+int KFind::find(const QString &text, const QString &pattern, int index, long options, int *matchedLength)
+{
+ // Handle regular expressions in the appropriate way.
+ if (options & KFindDialog::RegularExpression)
+ {
+ QRegExp regExp(pattern, options & KFindDialog::CaseSensitive);
+
+ return find(text, regExp, index, options, matchedLength);
+ }
+
+ bool caseSensitive = (options & KFindDialog::CaseSensitive);
+
+ if (options & KFindDialog::WholeWordsOnly)
+ {
+ if (options & KFindDialog::FindBackwards)
+ {
+ // Backward search, until the beginning of the line...
+ while (index >= 0)
+ {
+ // ...find the next match.
+ index = text.findRev(pattern, index, caseSensitive);
+ if (index == -1)
+ break;
+
+ // Is the match delimited correctly?
+ *matchedLength = pattern.length();
+ if (isWholeWords(text, index, *matchedLength))
+ break;
+ index--;
+ }
+ }
+ else
+ {
+ // Forward search, until the end of the line...
+ while (index < (int)text.length())
+ {
+ // ...find the next match.
+ index = text.find(pattern, index, caseSensitive);
+ if (index == -1)
+ break;
+
+ // Is the match delimited correctly?
+ *matchedLength = pattern.length();
+ if (isWholeWords(text, index, *matchedLength))
+ break;
+ index++;
+ }
+ if (index >= (int)text.length()) // end of line
+ index = -1; // not found
+ }
+ }
+ else
+ {
+ // Non-whole-word search.
+ if (options & KFindDialog::FindBackwards)
+ {
+ index = text.findRev(pattern, index, caseSensitive);
+ }
+ else
+ {
+ index = text.find(pattern, index, caseSensitive);
+ }
+ if (index != -1)
+ {
+ *matchedLength = pattern.length();
+ }
+ }
+ return index;
+}
+
+// static
+int KFind::find(const QString &text, const QRegExp &pattern, int index, long options, int *matchedLength)
+{
+ if (options & KFindDialog::WholeWordsOnly)
+ {
+ if (options & KFindDialog::FindBackwards)
+ {
+ // Backward search, until the beginning of the line...
+ while (index >= 0)
+ {
+ // ...find the next match.
+ index = text.findRev(pattern, index);
+ if (index == -1)
+ break;
+
+ // Is the match delimited correctly?
+ //pattern.match(text, index, matchedLength, false);
+ /*int pos =*/ pattern.search( text.mid(index) );
+ *matchedLength = pattern.matchedLength();
+ if (isWholeWords(text, index, *matchedLength))
+ break;
+ index--;
+ }
+ }
+ else
+ {
+ // Forward search, until the end of the line...
+ while (index < (int)text.length())
+ {
+ // ...find the next match.
+ index = text.find(pattern, index);
+ if (index == -1)
+ break;
+
+ // Is the match delimited correctly?
+ //pattern.match(text, index, matchedLength, false);
+ /*int pos =*/ pattern.search( text.mid(index) );
+ *matchedLength = pattern.matchedLength();
+ if (isWholeWords(text, index, *matchedLength))
+ break;
+ index++;
+ }
+ if (index >= (int)text.length()) // end of line
+ index = -1; // not found
+ }
+ }
+ else
+ {
+ // Non-whole-word search.
+ if (options & KFindDialog::FindBackwards)
+ {
+ index = text.findRev(pattern, index);
+ }
+ else
+ {
+ index = text.find(pattern, index);
+ }
+ if (index != -1)
+ {
+ //pattern.match(text, index, matchedLength, false);
+ /*int pos =*/ pattern.search( text.mid(index) );
+ *matchedLength = pattern.matchedLength();
+ }
+ }
+ return index;
+}
+
+bool KFind::isInWord(QChar ch)
+{
+ return ch.isLetter() || ch.isDigit() || ch == '_';
+}
+
+bool KFind::isWholeWords(const QString &text, int starts, int matchedLength)
+{
+ if ((starts == 0) || (!isInWord(text[starts - 1])))
+ {
+ int ends = starts + matchedLength;
+
+ if ((ends == (int)text.length()) || (!isInWord(text[ends])))
+ return true;
+ }
+ return false;
+}
+
+void KFind::slotFindNext()
+{
+ emit findNext();
+}
+
+void KFind::slotDialogClosed()
+{
+ emit dialogClosed();
+ m_dialogClosed = true;
+}
+
+void KFind::displayFinalDialog() const
+{
+ QString message;
+ if ( numMatches() )
+ message = i18n( "1 match found.", "%n matches found.", numMatches() );
+ else
+ message = i18n("<qt>No matches found for '<b>%1</b>'.</qt>").arg(QStyleSheet::escape(m_pattern));
+ KMessageBox::information(dialogsParent(), message);
+}
+
+bool KFind::shouldRestart( bool forceAsking, bool showNumMatches ) const
+{
+ // Only ask if we did a "find from cursor", otherwise it's pointless.
+ // Well, unless the user can modify the document during a search operation,
+ // hence the force boolean.
+ if ( !forceAsking && (m_options & KFindDialog::FromCursor) == 0 )
+ {
+ displayFinalDialog();
+ return false;
+ }
+ QString message;
+ if ( showNumMatches )
+ {
+ if ( numMatches() )
+ message = i18n( "1 match found.", "%n matches found.", numMatches() );
+ else
+ message = i18n("No matches found for '<b>%1</b>'.").arg(QStyleSheet::escape(m_pattern));
+ }
+ else
+ {
+ if ( m_options & KFindDialog::FindBackwards )
+ message = i18n( "Beginning of document reached." );
+ else
+ message = i18n( "End of document reached." );
+ }
+
+ message += "<br><br>"; // can't be in the i18n() of the first if() because of the plural form.
+ // Hope this word puzzle is ok, it's a different sentence
+ message +=
+ ( m_options & KFindDialog::FindBackwards ) ?
+ i18n("Continue from the end?")
+ : i18n("Continue from the beginning?");
+
+ int ret = KMessageBox::questionYesNo( dialogsParent(), QString("<qt>")+message+QString("</qt>"),
+ QString::null, KStdGuiItem::cont(), KStdGuiItem::stop() );
+ bool yes = ( ret == KMessageBox::Yes );
+ if ( yes )
+ const_cast<KFind*>(this)->m_options &= ~KFindDialog::FromCursor; // clear FromCursor option
+ return yes;
+}
+
+void KFind::setOptions( long options )
+{
+ m_options = options;
+
+ delete m_regExp;
+ if (m_options & KFindDialog::RegularExpression)
+ m_regExp = new QRegExp(m_pattern, m_options & KFindDialog::CaseSensitive);
+ else
+ m_regExp = 0;
+}
+
+void KFind::closeFindNextDialog()
+{
+ delete m_dialog;
+ m_dialog = 0L;
+ m_dialogClosed = true;
+}
+
+int KFind::index() const
+{
+ return m_index;
+}
+
+void KFind::setPattern( const QString& pattern )
+{
+ if ( m_options & KFindDialog::FindIncremental && m_pattern != pattern )
+ d->patternChanged = true;
+
+ m_pattern = pattern;
+ setOptions( options() ); // rebuild m_regExp if necessary
+}
+
+QWidget* KFind::dialogsParent() const
+{
+ // If the find dialog is still up, it should get the focus when closing a message box
+ // Otherwise, maybe the "find next?" dialog is up
+ // Otherwise, the "view" is the parent.
+ return d->findDialog ? (QWidget*)d->findDialog : ( m_dialog ? m_dialog : parentWidget() );
+}
+
+#include "kfind.moc"