kutils Library API Documentation

kfind.cpp

00001 /*
00002     Copyright (C) 2001, S.R.Haque <srhaque@iee.org>.
00003     Copyright (C) 2002, David Faure <david@mandrakesoft.com>
00004     Copyright (C) 2004, Arend van Beelen jr. <arend@auton.nl>
00005     This file is part of the KDE project
00006 
00007     This library is free software; you can redistribute it and/or
00008     modify it under the terms of the GNU Library General Public
00009     License version 2, as published by the Free Software Foundation.
00010 
00011     This library is distributed in the hope that it will be useful,
00012     but WITHOUT ANY WARRANTY; without even the implied warranty of
00013     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014     Library General Public License for more details.
00015 
00016     You should have received a copy of the GNU Library General Public License
00017     along with this library; see the file COPYING.LIB.  If not, write to
00018     the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
00019     Boston, MA 02111-1307, USA.
00020 */
00021 
00022 #include "kfind.h"
00023 #include "kfinddialog.h"
00024 #include <kapplication.h>
00025 #include <klocale.h>
00026 #include <kmessagebox.h>
00027 #include <qlabel.h>
00028 #include <qregexp.h>
00029 #include <qstylesheet.h>
00030 #include <qguardedptr.h>
00031 #include <qptrvector.h>
00032 #include <kdebug.h>
00033 
00034 //#define DEBUG_FIND
00035 
00036 #define INDEX_NOMATCH -1
00037 
00038 class KFindNextDialog : public KDialogBase
00039 {
00040 public:
00041     KFindNextDialog(const QString &pattern, QWidget *parent);
00042 };
00043 
00044 // Create the dialog.
00045 KFindNextDialog::KFindNextDialog(const QString &pattern, QWidget *parent) :
00046     KDialogBase(parent, 0, false,  // non-modal!
00047         i18n("Find Next"),
00048         User1 | Close,
00049         User1,
00050         false,
00051         i18n("&Find"))
00052 {
00053     setMainWidget( new QLabel( i18n("<qt>Find next occurrence of '<b>%1</b>'?</qt>").arg(pattern), this ) );
00054 }
00055 
00057 
00058 struct KFind::Private
00059 {
00060     Private() :
00061       findDialog(0),
00062       patternChanged(false),
00063       matchedPattern(""),
00064       incrementalPath(29, true),
00065       emptyMatch(0),
00066       currentId(0),
00067       customIds(false)
00068     {
00069         incrementalPath.setAutoDelete(true);
00070         data.setAutoDelete(true);
00071     }
00072 
00073     ~Private()
00074     {
00075         delete emptyMatch;
00076         emptyMatch = 0;
00077     }
00078 
00079     struct Match
00080     {
00081         Match(int dataId, int index, int matchedLength) :
00082           dataId(dataId),
00083           index(index),
00084           matchedLength(matchedLength)
00085         { }
00086 
00087         int dataId;
00088         int index;
00089         int matchedLength;
00090     };
00091 
00092     struct Data
00093     {
00094         Data() : id(-1), dirty(false) { }
00095         Data(int id, const QString &text, bool dirty = false) :
00096           id(id),
00097           text(text),
00098           dirty(dirty)
00099         { }
00100 
00101         int     id;
00102         QString text;
00103         bool    dirty;
00104     };
00105 
00106     QGuardedPtr<QWidget>  findDialog;
00107     bool                  patternChanged;
00108     QString               matchedPattern;
00109     QDict<Match>          incrementalPath;
00110     Match *               emptyMatch;
00111     QPtrVector<Data>      data;
00112     int                   currentId;
00113     bool                  customIds;
00114 };
00115 
00117 
00118 KFind::KFind( const QString &pattern, long options, QWidget *parent )
00119     : QObject( parent )
00120 {
00121     d = new KFind::Private;
00122     m_options = options;
00123     init( pattern );
00124 }
00125 
00126 KFind::KFind( const QString &pattern, long options, QWidget *parent, QWidget *findDialog )
00127     : QObject( parent )
00128 {
00129     d = new KFind::Private;
00130     d->findDialog = findDialog;
00131     m_options = options;
00132     init( pattern );
00133 }
00134 
00135 void KFind::init( const QString& pattern )
00136 {
00137     m_matches = 0;
00138     m_pattern = pattern;
00139     m_dialog = 0;
00140     m_dialogClosed = false;
00141     m_index = INDEX_NOMATCH;
00142     m_lastResult = NoMatch;
00143     if (m_options & KFindDialog::RegularExpression)
00144         m_regExp = new QRegExp(pattern, m_options & KFindDialog::CaseSensitive);
00145     else {
00146         m_regExp = 0;
00147     }
00148 }
00149 
00150 KFind::~KFind()
00151 {
00152     delete m_dialog;
00153     delete d;
00154 }
00155 
00156 bool KFind::needData() const
00157 {
00158     // always true when m_text is empty.
00159     if (m_options & KFindDialog::FindBackwards)
00160         // m_index==-1 and m_lastResult==Match means we haven't answered nomatch yet
00161         // This is important in the "replace with a prompt" case.
00162         return ( m_index < 0 && m_lastResult != Match );
00163     else
00164         // "index over length" test removed: we want to get a nomatch before we set data again
00165         // This is important in the "replace with a prompt" case.
00166         return m_index == INDEX_NOMATCH;
00167 }
00168 
00169 void KFind::setData( const QString& data, int startPos )
00170 {
00171     setData( -1, data, startPos );
00172 }
00173 
00174 void KFind::setData( int id, const QString& data, int startPos )
00175 {
00176     // cache the data for incremental find
00177     if ( m_options & KFindDialog::FindIncremental )
00178     {
00179         if ( id == -1 )
00180             id = d->currentId + 1;
00181 
00182         if ( id >= (int) d->data.size() )
00183             d->data.resize( id + 100 );
00184 
00185         if ( id != -1 )
00186             d->customIds = true;
00187 
00188         d->data.insert( id, new Private::Data(id, data, true) );
00189     }
00190 
00191     if ( !(m_options & KFindDialog::FindIncremental) || needData() )
00192     {
00193         m_text = data;
00194 
00195         if ( startPos != -1 )
00196             m_index = startPos;
00197         else if (m_options & KFindDialog::FindBackwards)
00198             m_index = m_text.length();
00199         else
00200             m_index = 0;
00201 #ifdef DEBUG_FIND
00202         kdDebug() << "setData: '" << m_text << "' m_index=" << m_index << endl;
00203 #endif
00204         Q_ASSERT( m_index != INDEX_NOMATCH );
00205         m_lastResult = NoMatch;
00206 
00207         d->currentId = id;
00208     }
00209 }
00210 
00211 KDialogBase* KFind::findNextDialog( bool create )
00212 {
00213     if ( !m_dialog && create )
00214     {
00215         m_dialog = new KFindNextDialog( m_pattern, parentWidget() );
00216         connect( m_dialog, SIGNAL( user1Clicked() ), this, SLOT( slotFindNext() ) );
00217         connect( m_dialog, SIGNAL( finished() ), this, SLOT( slotDialogClosed() ) );
00218     }
00219     return m_dialog;
00220 }
00221 
00222 KFind::Result KFind::find()
00223 {
00224     Q_ASSERT( m_index != INDEX_NOMATCH || d->patternChanged );
00225 
00226     if ( m_lastResult == Match && !d->patternChanged )
00227     {
00228         // Move on before looking for the next match, _if_ we just found a match
00229         if (m_options & KFindDialog::FindBackwards) {
00230             m_index--;
00231             if ( m_index == -1 ) // don't call KFind::find with -1, it has a special meaning
00232             {
00233                 m_lastResult = NoMatch;
00234                 return NoMatch;
00235             }
00236         } else
00237             m_index++;
00238     }
00239     d->patternChanged = false;
00240 
00241     if ( m_options & KFindDialog::FindIncremental )
00242     {
00243         // if the current pattern is shorter than the matchedPattern we can
00244         // probably look up the match in the incrementalPath
00245         if ( m_pattern.length() < d->matchedPattern.length() )
00246         {
00247             Private::Match *match = m_pattern.isEmpty() ? d->emptyMatch : d->incrementalPath[m_pattern];
00248             QString previousPattern = d->matchedPattern;
00249             d->matchedPattern = m_pattern;
00250             if ( match != 0 )
00251             {
00252                 bool clean = true;
00253 
00254                 // find the first result backwards on the path that isn't dirty
00255                 while ( d->data[match->dataId]->dirty == true &&
00256                         !m_pattern.isEmpty() )
00257                 {
00258                     m_pattern.truncate( m_pattern.length() - 1 );
00259 
00260                     match = d->incrementalPath[m_pattern];
00261 
00262                     clean = false;
00263                 }
00264 
00265                 // remove all matches that lie after the current match
00266                 while ( m_pattern.length() < previousPattern.length() )
00267                 {
00268                     d->incrementalPath.remove(previousPattern);
00269                     previousPattern.truncate(previousPattern.length() - 1);
00270                 }
00271 
00272                 // set the current text, index, etc. to the found match
00273                 m_text = d->data[match->dataId]->text;
00274                 m_index = match->index;
00275                 m_matchedLength = match->matchedLength;
00276                 d->currentId = match->dataId;
00277 
00278                 // if the result is clean we can return it now
00279                 if ( clean )
00280                 {
00281                     if ( d->customIds )
00282                         emit highlight(d->currentId, m_index, m_matchedLength);
00283                     else
00284                         emit highlight(m_text, m_index, m_matchedLength);
00285 
00286                     m_lastResult = Match;
00287                     d->matchedPattern = m_pattern;
00288                     return Match;
00289                 }
00290             }
00291             // if we couldn't look up the match, the new pattern isn't a
00292             // substring of the matchedPattern, so we start a new search
00293             else
00294             {
00295                 startNewIncrementalSearch();
00296             }
00297         }
00298         // if the new pattern is longer than the matchedPattern we might be
00299         // able to proceed from the last search
00300         else if ( m_pattern.length() > d->matchedPattern.length() )
00301         {
00302             // continue from the previous pattern
00303             if ( m_pattern.startsWith(d->matchedPattern) )
00304             {
00305                 // we can't proceed from the previous position if the previous
00306                 // position already failed
00307                 if ( m_index == INDEX_NOMATCH )
00308                     return NoMatch;
00309 
00310                 QString temp = m_pattern;
00311                 m_pattern.truncate(d->matchedPattern.length() + 1);
00312                 d->matchedPattern = temp;
00313             }
00314             // start a new search
00315             else
00316             {
00317                 startNewIncrementalSearch();
00318             }
00319         }
00320         // if the new pattern is as long as the matchedPattern, we reset if
00321         // they are not equal
00322         else if ( m_pattern != d->matchedPattern )
00323         {
00324              startNewIncrementalSearch();
00325         }
00326     }
00327 
00328 #ifdef DEBUG_FIND
00329     kdDebug() << k_funcinfo << "m_index=" << m_index << endl;
00330 #endif
00331     do
00332     {
00333         // if we have multiple data blocks in our cache, walk through these
00334         // blocks till we either searched all blocks or we find a match
00335         do
00336         {
00337             // Find the next candidate match.
00338             if ( m_options & KFindDialog::RegularExpression )
00339                 m_index = KFind::find(m_text, *m_regExp, m_index, m_options, &m_matchedLength);
00340             else
00341                 m_index = KFind::find(m_text, m_pattern, m_index, m_options, &m_matchedLength);
00342 
00343             if ( m_options & KFindDialog::FindIncremental )
00344                 d->data[d->currentId]->dirty = false;
00345 
00346             if ( m_index == -1 && d->currentId < (int) d->data.count() - 1 )
00347             {
00348                 m_text = d->data[++d->currentId]->text;
00349 
00350                 if ( m_options & KFindDialog::FindBackwards )
00351                     m_index = m_text.length();
00352                 else
00353                     m_index = 0;
00354             }
00355             else
00356                 break;
00357         } while ( !(m_options & KFindDialog::RegularExpression) );
00358 
00359         if ( m_index != -1 )
00360         {
00361             // Flexibility: the app can add more rules to validate a possible match
00362             if ( validateMatch( m_text, m_index, m_matchedLength ) )
00363             {
00364                 bool done = true;
00365 
00366                 if ( m_options & KFindDialog::FindIncremental )
00367                 {
00368                     if ( m_pattern.isEmpty() ) {
00369                         delete d->emptyMatch;
00370                         d->emptyMatch = new Private::Match( d->currentId, m_index, m_matchedLength );
00371                     } else
00372                         d->incrementalPath.replace(m_pattern, new Private::Match(d->currentId, m_index, m_matchedLength));
00373 
00374                     if ( m_pattern.length() < d->matchedPattern.length() )
00375                     {
00376                         m_pattern += d->matchedPattern.mid(m_pattern.length(), 1);
00377                         done = false;
00378                     }
00379                 }
00380 
00381                 if ( done )
00382                 {
00383                     m_matches++;
00384                     // Tell the world about the match we found, in case someone wants to
00385                     // highlight it.
00386                     if ( d->customIds )
00387                         emit highlight(d->currentId, m_index, m_matchedLength);
00388                     else
00389                         emit highlight(m_text, m_index, m_matchedLength);
00390 
00391                     if ( !m_dialogClosed )
00392                         findNextDialog(true)->show();
00393 
00394 #ifdef DEBUG_FIND
00395                     kdDebug() << k_funcinfo << "Match. Next m_index=" << m_index << endl;
00396 #endif
00397                     m_lastResult = Match;
00398                     return Match;
00399                 }
00400             }
00401             else // Skip match
00402             {
00403                 if (m_options & KFindDialog::FindBackwards)
00404                     m_index--;
00405                 else
00406                     m_index++;
00407             }
00408         }
00409         else
00410         {
00411             if ( m_options & KFindDialog::FindIncremental )
00412             {
00413                 QString temp = m_pattern;
00414                 temp.truncate(temp.length() - 1);
00415                 m_pattern = d->matchedPattern;
00416                 d->matchedPattern = temp;
00417             }
00418 
00419             m_index = INDEX_NOMATCH;
00420         }
00421     }
00422     while (m_index != INDEX_NOMATCH);
00423 
00424 #ifdef DEBUG_FIND
00425     kdDebug() << k_funcinfo << "NoMatch. m_index=" << m_index << endl;
00426 #endif
00427     m_lastResult = NoMatch;
00428     return NoMatch;
00429 }
00430 
00431 void KFind::startNewIncrementalSearch()
00432 {
00433     Private::Match *match = d->emptyMatch;
00434     if(match == 0)
00435     {
00436         m_text = QString::null;
00437         m_index = 0;
00438         d->currentId = 0;
00439     }
00440     else
00441     {
00442         m_text = d->data[match->dataId]->text;
00443         m_index = match->index;
00444         d->currentId = match->dataId;
00445     }
00446     m_matchedLength = 0;
00447     d->incrementalPath.clear();
00448     delete d->emptyMatch;
00449     d->emptyMatch = 0;
00450     d->matchedPattern = m_pattern;
00451     m_pattern = QString::null;
00452 }
00453 
00454 // static
00455 int KFind::find(const QString &text, const QString &pattern, int index, long options, int *matchedLength)
00456 {
00457     // Handle regular expressions in the appropriate way.
00458     if (options & KFindDialog::RegularExpression)
00459     {
00460         QRegExp regExp(pattern, options & KFindDialog::CaseSensitive);
00461 
00462         return find(text, regExp, index, options, matchedLength);
00463     }
00464 
00465     bool caseSensitive = (options & KFindDialog::CaseSensitive);
00466 
00467     if (options & KFindDialog::WholeWordsOnly)
00468     {
00469         if (options & KFindDialog::FindBackwards)
00470         {
00471             // Backward search, until the beginning of the line...
00472             while (index >= 0)
00473             {
00474                 // ...find the next match.
00475                 index = text.findRev(pattern, index, caseSensitive);
00476                 if (index == -1)
00477                     break;
00478 
00479                 // Is the match delimited correctly?
00480                 *matchedLength = pattern.length();
00481                 if (isWholeWords(text, index, *matchedLength))
00482                     break;
00483                 index--;
00484             }
00485         }
00486         else
00487         {
00488             // Forward search, until the end of the line...
00489             while (index < (int)text.length())
00490             {
00491                 // ...find the next match.
00492                 index = text.find(pattern, index, caseSensitive);
00493                 if (index == -1)
00494                     break;
00495 
00496                 // Is the match delimited correctly?
00497                 *matchedLength = pattern.length();
00498                 if (isWholeWords(text, index, *matchedLength))
00499                     break;
00500                 index++;
00501             }
00502             if (index >= (int)text.length()) // end of line
00503                 index = -1; // not found
00504         }
00505     }
00506     else
00507     {
00508         // Non-whole-word search.
00509         if (options & KFindDialog::FindBackwards)
00510         {
00511             index = text.findRev(pattern, index, caseSensitive);
00512         }
00513         else
00514         {
00515             index = text.find(pattern, index, caseSensitive);
00516         }
00517         if (index != -1)
00518         {
00519             *matchedLength = pattern.length();
00520         }
00521     }
00522     return index;
00523 }
00524 
00525 // static
00526 int KFind::find(const QString &text, const QRegExp &pattern, int index, long options, int *matchedLength)
00527 {
00528     if (options & KFindDialog::WholeWordsOnly)
00529     {
00530         if (options & KFindDialog::FindBackwards)
00531         {
00532             // Backward search, until the beginning of the line...
00533             while (index >= 0)
00534             {
00535                 // ...find the next match.
00536                 index = text.findRev(pattern, index);
00537                 if (index == -1)
00538                     break;
00539 
00540                 // Is the match delimited correctly?
00541                 //pattern.match(text, index, matchedLength, false);
00542                 /*int pos =*/ pattern.search( text.mid(index) );
00543                 *matchedLength = pattern.matchedLength();
00544                 if (isWholeWords(text, index, *matchedLength))
00545                     break;
00546                 index--;
00547             }
00548         }
00549         else
00550         {
00551             // Forward search, until the end of the line...
00552             while (index < (int)text.length())
00553             {
00554                 // ...find the next match.
00555                 index = text.find(pattern, index);
00556                 if (index == -1)
00557                     break;
00558 
00559                 // Is the match delimited correctly?
00560                 //pattern.match(text, index, matchedLength, false);
00561                 /*int pos =*/ pattern.search( text.mid(index) );
00562                 *matchedLength = pattern.matchedLength();
00563                 if (isWholeWords(text, index, *matchedLength))
00564                     break;
00565                 index++;
00566             }
00567             if (index >= (int)text.length()) // end of line
00568                 index = -1; // not found
00569         }
00570     }
00571     else
00572     {
00573         // Non-whole-word search.
00574         if (options & KFindDialog::FindBackwards)
00575         {
00576             index = text.findRev(pattern, index);
00577         }
00578         else
00579         {
00580             index = text.find(pattern, index);
00581         }
00582         if (index != -1)
00583         {
00584             //pattern.match(text, index, matchedLength, false);
00585             /*int pos =*/ pattern.search( text.mid(index) );
00586             *matchedLength = pattern.matchedLength();
00587         }
00588     }
00589     return index;
00590 }
00591 
00592 bool KFind::isInWord(QChar ch)
00593 {
00594     return ch.isLetter() || ch.isDigit() || ch == '_';
00595 }
00596 
00597 bool KFind::isWholeWords(const QString &text, int starts, int matchedLength)
00598 {
00599     if ((starts == 0) || (!isInWord(text[starts - 1])))
00600     {
00601         int ends = starts + matchedLength;
00602 
00603         if ((ends == (int)text.length()) || (!isInWord(text[ends])))
00604             return true;
00605     }
00606     return false;
00607 }
00608 
00609 void KFind::slotFindNext()
00610 {
00611     emit findNext();
00612 }
00613 
00614 void KFind::slotDialogClosed()
00615 {
00616     emit dialogClosed();
00617     m_dialogClosed = true;
00618 }
00619 
00620 void KFind::displayFinalDialog() const
00621 {
00622     QString message;
00623     if ( numMatches() )
00624         message = i18n( "1 match found.", "%n matches found.", numMatches() );
00625     else
00626         message = i18n("<qt>No matches found for '<b>%1</b>'.</qt>").arg(QStyleSheet::escape(m_pattern));
00627     KMessageBox::information(dialogsParent(), message);
00628 }
00629 
00630 bool KFind::shouldRestart( bool forceAsking, bool showNumMatches ) const
00631 {
00632     // Only ask if we did a "find from cursor", otherwise it's pointless.
00633     // Well, unless the user can modify the document during a search operation,
00634     // hence the force boolean.
00635     if ( !forceAsking && (m_options & KFindDialog::FromCursor) == 0 )
00636     {
00637         displayFinalDialog();
00638         return false;
00639     }
00640     QString message;
00641     if ( showNumMatches )
00642     {
00643         if ( numMatches() )
00644             message = i18n( "1 match found.", "%n matches found.", numMatches() );
00645         else
00646             message = i18n("No matches found for '<b>%1</b>'.").arg(QStyleSheet::escape(m_pattern));
00647     }
00648     else
00649     {
00650         if ( m_options & KFindDialog::FindBackwards )
00651             message = i18n( "Beginning of document reached." );
00652         else
00653             message = i18n( "End of document reached." );
00654     }
00655 
00656     message += "\n"; // can't be in the i18n() of the first if() because of the plural form.
00657     // Hope this word puzzle is ok, it's a different sentence
00658     message +=
00659         ( m_options & KFindDialog::FindBackwards ) ?
00660         i18n("Do you want to restart search from the end?")
00661         : i18n("Do you want to restart search at the beginning?");
00662 
00663     int ret = KMessageBox::questionYesNo( dialogsParent(), QString("<qt>")+message+QString("</qt>") );
00664     bool yes = ( ret == KMessageBox::Yes );
00665     if ( yes )
00666         const_cast<KFind*>(this)->m_options &= ~KFindDialog::FromCursor; // clear FromCursor option
00667     return yes;
00668 }
00669 
00670 void KFind::setOptions( long options )
00671 {
00672     m_options = options;
00673 
00674     delete m_regExp;
00675     if (m_options & KFindDialog::RegularExpression)
00676         m_regExp = new QRegExp(m_pattern, m_options & KFindDialog::CaseSensitive);
00677     else
00678         m_regExp = 0;
00679 }
00680 
00681 void KFind::closeFindNextDialog()
00682 {
00683     delete m_dialog;
00684     m_dialog = 0L;
00685     m_dialogClosed = true;
00686 }
00687 
00688 int KFind::index() const
00689 {
00690     return m_index;
00691 }
00692 
00693 void KFind::setPattern( const QString& pattern )
00694 {
00695     if ( m_options & KFindDialog::FindIncremental && m_pattern != pattern )
00696         d->patternChanged = true;
00697 
00698     m_pattern = pattern;
00699     setOptions( options() ); // rebuild m_regExp if necessary
00700 }
00701 
00702 QWidget* KFind::dialogsParent() const
00703 {
00704     // If the find dialog is still up, it should get the focus when closing a message box
00705     // Otherwise, maybe the "find next?" dialog is up
00706     // Otherwise, the "view" is the parent.
00707     return d->findDialog ? (QWidget*)d->findDialog : ( m_dialog ? m_dialog : parentWidget() );
00708 }
00709 
00710 #include "kfind.moc"
KDE Logo
This file is part of the documentation for kutils Library Version 3.4.2.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Wed Feb 8 08:03:16 2006 by doxygen 1.4.4 written by Dimitri van Heesch, © 1997-2003