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., 51 Franklin Street, Fifth Floor, 00019 Boston, MA 02110-1301, 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 <tqlabel.h> 00028 #include <tqregexp.h> 00029 #include <tqstylesheet.h> 00030 #include <tqguardedptr.h> 00031 #include <tqptrvector.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 TQString &pattern, TQWidget *parent); 00042 }; 00043 00044 // Create the dialog. 00045 KFindNextDialog::KFindNextDialog(const TQString &pattern, TQWidget *parent) : 00046 KDialogBase(parent, 0, false, // non-modal! 00047 i18n("Find Next"), 00048 User1 | Close, 00049 User1, 00050 false, 00051 KStdGuiItem::find()) 00052 { 00053 setMainWidget( new TQLabel( 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 TQString &text, bool dirty = false) : 00096 id(id), 00097 text(text), 00098 dirty(dirty) 00099 { } 00100 00101 int id; 00102 TQString text; 00103 bool dirty; 00104 }; 00105 00106 TQGuardedPtr<TQWidget> findDialog; 00107 bool patternChanged; 00108 TQString matchedPattern; 00109 TQDict<Match> incrementalPath; 00110 Match * emptyMatch; 00111 TQPtrVector<Data> data; 00112 int currentId; 00113 bool customIds; 00114 }; 00115 00117 00118 KFind::KFind( const TQString &pattern, long options, TQWidget *parent ) 00119 : TQObject( parent ) 00120 { 00121 d = new KFind::Private; 00122 m_options = options; 00123 init( pattern ); 00124 } 00125 00126 KFind::KFind( const TQString &pattern, long options, TQWidget *parent, TQWidget *findDialog ) 00127 : TQObject( 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 TQString& 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 TQRegExp(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 TQString& data, int startPos ) 00170 { 00171 setData( -1, data, startPos ); 00172 } 00173 00174 void KFind::setData( int id, const TQString& data, int startPos ) 00175 { 00176 // cache the data for incremental find 00177 if ( m_options & KFindDialog::FindIncremental ) 00178 { 00179 if ( id != -1 ) 00180 d->customIds = true; 00181 else 00182 id = d->currentId + 1; 00183 00184 if ( id >= (int) d->data.size() ) 00185 d->data.resize( id + 100 ); 00186 00187 d->data.insert( id, new Private::Data(id, data, true) ); 00188 } 00189 00190 if ( !(m_options & KFindDialog::FindIncremental) || needData() ) 00191 { 00192 m_text = data; 00193 00194 if ( startPos != -1 ) 00195 m_index = startPos; 00196 else if (m_options & KFindDialog::FindBackwards) 00197 m_index = m_text.length(); 00198 else 00199 m_index = 0; 00200 #ifdef DEBUG_FIND 00201 kdDebug() << "setData: '" << m_text << "' m_index=" << m_index << endl; 00202 #endif 00203 Q_ASSERT( m_index != INDEX_NOMATCH ); 00204 m_lastResult = NoMatch; 00205 00206 d->currentId = id; 00207 } 00208 } 00209 00210 KDialogBase* KFind::findNextDialog( bool create ) 00211 { 00212 if ( !m_dialog && create ) 00213 { 00214 m_dialog = new KFindNextDialog( m_pattern, parentWidget() ); 00215 connect( m_dialog, TQT_SIGNAL( user1Clicked() ), this, TQT_SLOT( slotFindNext() ) ); 00216 connect( m_dialog, TQT_SIGNAL( finished() ), this, TQT_SLOT( slotDialogClosed() ) ); 00217 } 00218 return m_dialog; 00219 } 00220 00221 KFind::Result KFind::find() 00222 { 00223 Q_ASSERT( m_index != INDEX_NOMATCH || d->patternChanged ); 00224 00225 if ( m_lastResult == Match && !d->patternChanged ) 00226 { 00227 // Move on before looking for the next match, _if_ we just found a match 00228 if (m_options & KFindDialog::FindBackwards) { 00229 m_index--; 00230 if ( m_index == -1 ) // don't call KFind::find with -1, it has a special meaning 00231 { 00232 m_lastResult = NoMatch; 00233 return NoMatch; 00234 } 00235 } else 00236 m_index++; 00237 } 00238 d->patternChanged = false; 00239 00240 if ( m_options & KFindDialog::FindIncremental ) 00241 { 00242 // if the current pattern is shorter than the matchedPattern we can 00243 // probably look up the match in the incrementalPath 00244 if ( m_pattern.length() < d->matchedPattern.length() ) 00245 { 00246 Private::Match *match = m_pattern.isEmpty() ? d->emptyMatch : d->incrementalPath[m_pattern]; 00247 TQString previousPattern = d->matchedPattern; 00248 d->matchedPattern = m_pattern; 00249 if ( match != 0 ) 00250 { 00251 bool clean = true; 00252 00253 // find the first result backwards on the path that isn't dirty 00254 while ( d->data[match->dataId]->dirty == true && 00255 !m_pattern.isEmpty() ) 00256 { 00257 m_pattern.truncate( m_pattern.length() - 1 ); 00258 00259 match = d->incrementalPath[m_pattern]; 00260 00261 clean = false; 00262 } 00263 00264 // remove all matches that lie after the current match 00265 while ( m_pattern.length() < previousPattern.length() ) 00266 { 00267 d->incrementalPath.remove(previousPattern); 00268 previousPattern.truncate(previousPattern.length() - 1); 00269 } 00270 00271 // set the current text, index, etc. to the found match 00272 m_text = d->data[match->dataId]->text; 00273 m_index = match->index; 00274 m_matchedLength = match->matchedLength; 00275 d->currentId = match->dataId; 00276 00277 // if the result is clean we can return it now 00278 if ( clean ) 00279 { 00280 if ( d->customIds ) 00281 emit highlight(d->currentId, m_index, m_matchedLength); 00282 else 00283 emit highlight(m_text, m_index, m_matchedLength); 00284 00285 m_lastResult = Match; 00286 d->matchedPattern = m_pattern; 00287 return Match; 00288 } 00289 } 00290 // if we couldn't look up the match, the new pattern isn't a 00291 // substring of the matchedPattern, so we start a new search 00292 else 00293 { 00294 startNewIncrementalSearch(); 00295 } 00296 } 00297 // if the new pattern is longer than the matchedPattern we might be 00298 // able to proceed from the last search 00299 else if ( m_pattern.length() > d->matchedPattern.length() ) 00300 { 00301 // continue from the previous pattern 00302 if ( m_pattern.startsWith(d->matchedPattern) ) 00303 { 00304 // we can't proceed from the previous position if the previous 00305 // position already failed 00306 if ( m_index == INDEX_NOMATCH ) 00307 return NoMatch; 00308 00309 TQString temp = m_pattern; 00310 m_pattern.truncate(d->matchedPattern.length() + 1); 00311 d->matchedPattern = temp; 00312 } 00313 // start a new search 00314 else 00315 { 00316 startNewIncrementalSearch(); 00317 } 00318 } 00319 // if the new pattern is as long as the matchedPattern, we reset if 00320 // they are not equal 00321 else if ( m_pattern != d->matchedPattern ) 00322 { 00323 startNewIncrementalSearch(); 00324 } 00325 } 00326 00327 #ifdef DEBUG_FIND 00328 kdDebug() << k_funcinfo << "m_index=" << m_index << endl; 00329 #endif 00330 do 00331 { 00332 // if we have multiple data blocks in our cache, walk through these 00333 // blocks till we either searched all blocks or we find a match 00334 do 00335 { 00336 // Find the next candidate match. 00337 if ( m_options & KFindDialog::RegularExpression ) 00338 m_index = KFind::find(m_text, *m_regExp, m_index, m_options, &m_matchedLength); 00339 else 00340 m_index = KFind::find(m_text, m_pattern, m_index, m_options, &m_matchedLength); 00341 00342 if ( m_options & KFindDialog::FindIncremental ) 00343 d->data[d->currentId]->dirty = false; 00344 00345 if ( m_index == -1 && d->currentId < (int) d->data.count() - 1 ) 00346 { 00347 m_text = d->data[++d->currentId]->text; 00348 00349 if ( m_options & KFindDialog::FindBackwards ) 00350 m_index = m_text.length(); 00351 else 00352 m_index = 0; 00353 } 00354 else 00355 break; 00356 } while ( !(m_options & KFindDialog::RegularExpression) ); 00357 00358 if ( m_index != -1 ) 00359 { 00360 // Flexibility: the app can add more rules to validate a possible match 00361 if ( validateMatch( m_text, m_index, m_matchedLength ) ) 00362 { 00363 bool done = true; 00364 00365 if ( m_options & KFindDialog::FindIncremental ) 00366 { 00367 if ( m_pattern.isEmpty() ) { 00368 delete d->emptyMatch; 00369 d->emptyMatch = new Private::Match( d->currentId, m_index, m_matchedLength ); 00370 } else 00371 d->incrementalPath.replace(m_pattern, new Private::Match(d->currentId, m_index, m_matchedLength)); 00372 00373 if ( m_pattern.length() < d->matchedPattern.length() ) 00374 { 00375 m_pattern += d->matchedPattern.mid(m_pattern.length(), 1); 00376 done = false; 00377 } 00378 } 00379 00380 if ( done ) 00381 { 00382 m_matches++; 00383 // Tell the world about the match we found, in case someone wants to 00384 // highlight it. 00385 if ( d->customIds ) 00386 emit highlight(d->currentId, m_index, m_matchedLength); 00387 else 00388 emit highlight(m_text, m_index, m_matchedLength); 00389 00390 if ( !m_dialogClosed ) 00391 findNextDialog(true)->show(); 00392 00393 #ifdef DEBUG_FIND 00394 kdDebug() << k_funcinfo << "Match. Next m_index=" << m_index << endl; 00395 #endif 00396 m_lastResult = Match; 00397 return Match; 00398 } 00399 } 00400 else // Skip match 00401 { 00402 if (m_options & KFindDialog::FindBackwards) 00403 m_index--; 00404 else 00405 m_index++; 00406 } 00407 } 00408 else 00409 { 00410 if ( m_options & KFindDialog::FindIncremental ) 00411 { 00412 TQString temp = m_pattern; 00413 temp.truncate(temp.length() - 1); 00414 m_pattern = d->matchedPattern; 00415 d->matchedPattern = temp; 00416 } 00417 00418 m_index = INDEX_NOMATCH; 00419 } 00420 } 00421 while (m_index != INDEX_NOMATCH); 00422 00423 #ifdef DEBUG_FIND 00424 kdDebug() << k_funcinfo << "NoMatch. m_index=" << m_index << endl; 00425 #endif 00426 m_lastResult = NoMatch; 00427 return NoMatch; 00428 } 00429 00430 void KFind::startNewIncrementalSearch() 00431 { 00432 Private::Match *match = d->emptyMatch; 00433 if(match == 0) 00434 { 00435 m_text = TQString::null; 00436 m_index = 0; 00437 d->currentId = 0; 00438 } 00439 else 00440 { 00441 m_text = d->data[match->dataId]->text; 00442 m_index = match->index; 00443 d->currentId = match->dataId; 00444 } 00445 m_matchedLength = 0; 00446 d->incrementalPath.clear(); 00447 delete d->emptyMatch; 00448 d->emptyMatch = 0; 00449 d->matchedPattern = m_pattern; 00450 m_pattern = TQString::null; 00451 } 00452 00453 // static 00454 int KFind::find(const TQString &text, const TQString &pattern, int index, long options, int *matchedLength) 00455 { 00456 // Handle regular expressions in the appropriate way. 00457 if (options & KFindDialog::RegularExpression) 00458 { 00459 TQRegExp regExp(pattern, options & KFindDialog::CaseSensitive); 00460 00461 return find(text, regExp, index, options, matchedLength); 00462 } 00463 00464 bool caseSensitive = (options & KFindDialog::CaseSensitive); 00465 00466 if (options & KFindDialog::WholeWordsOnly) 00467 { 00468 if (options & KFindDialog::FindBackwards) 00469 { 00470 // Backward search, until the beginning of the line... 00471 while (index >= 0) 00472 { 00473 // ...find the next match. 00474 index = text.findRev(pattern, index, caseSensitive); 00475 if (index == -1) 00476 break; 00477 00478 // Is the match delimited correctly? 00479 *matchedLength = pattern.length(); 00480 if (isWholeWords(text, index, *matchedLength)) 00481 break; 00482 index--; 00483 } 00484 } 00485 else 00486 { 00487 // Forward search, until the end of the line... 00488 while (index < (int)text.length()) 00489 { 00490 // ...find the next match. 00491 index = text.find(pattern, index, caseSensitive); 00492 if (index == -1) 00493 break; 00494 00495 // Is the match delimited correctly? 00496 *matchedLength = pattern.length(); 00497 if (isWholeWords(text, index, *matchedLength)) 00498 break; 00499 index++; 00500 } 00501 if (index >= (int)text.length()) // end of line 00502 index = -1; // not found 00503 } 00504 } 00505 else 00506 { 00507 // Non-whole-word search. 00508 if (options & KFindDialog::FindBackwards) 00509 { 00510 index = text.findRev(pattern, index, caseSensitive); 00511 } 00512 else 00513 { 00514 index = text.find(pattern, index, caseSensitive); 00515 } 00516 if (index != -1) 00517 { 00518 *matchedLength = pattern.length(); 00519 } 00520 } 00521 return index; 00522 } 00523 00524 // static 00525 int KFind::find(const TQString &text, const TQRegExp &pattern, int index, long options, int *matchedLength) 00526 { 00527 if (options & KFindDialog::WholeWordsOnly) 00528 { 00529 if (options & KFindDialog::FindBackwards) 00530 { 00531 // Backward search, until the beginning of the line... 00532 while (index >= 0) 00533 { 00534 // ...find the next match. 00535 index = text.findRev(pattern, index); 00536 if (index == -1) 00537 break; 00538 00539 // Is the match delimited correctly? 00540 //pattern.match(text, index, matchedLength, false); 00541 /*int pos =*/ pattern.search( text.mid(index) ); 00542 *matchedLength = pattern.matchedLength(); 00543 if (isWholeWords(text, index, *matchedLength)) 00544 break; 00545 index--; 00546 } 00547 } 00548 else 00549 { 00550 // Forward search, until the end of the line... 00551 while (index < (int)text.length()) 00552 { 00553 // ...find the next match. 00554 index = text.find(pattern, index); 00555 if (index == -1) 00556 break; 00557 00558 // Is the match delimited correctly? 00559 //pattern.match(text, index, matchedLength, false); 00560 /*int pos =*/ pattern.search( text.mid(index) ); 00561 *matchedLength = pattern.matchedLength(); 00562 if (isWholeWords(text, index, *matchedLength)) 00563 break; 00564 index++; 00565 } 00566 if (index >= (int)text.length()) // end of line 00567 index = -1; // not found 00568 } 00569 } 00570 else 00571 { 00572 // Non-whole-word search. 00573 if (options & KFindDialog::FindBackwards) 00574 { 00575 index = text.findRev(pattern, index); 00576 } 00577 else 00578 { 00579 index = text.find(pattern, index); 00580 } 00581 if (index != -1) 00582 { 00583 //pattern.match(text, index, matchedLength, false); 00584 /*int pos =*/ pattern.search( text.mid(index) ); 00585 *matchedLength = pattern.matchedLength(); 00586 } 00587 } 00588 return index; 00589 } 00590 00591 bool KFind::isInWord(TQChar ch) 00592 { 00593 return ch.isLetter() || ch.isDigit() || ch == '_'; 00594 } 00595 00596 bool KFind::isWholeWords(const TQString &text, int starts, int matchedLength) 00597 { 00598 if ((starts == 0) || (!isInWord(text[starts - 1]))) 00599 { 00600 int ends = starts + matchedLength; 00601 00602 if ((ends == (int)text.length()) || (!isInWord(text[ends]))) 00603 return true; 00604 } 00605 return false; 00606 } 00607 00608 void KFind::slotFindNext() 00609 { 00610 emit findNext(); 00611 } 00612 00613 void KFind::slotDialogClosed() 00614 { 00615 emit dialogClosed(); 00616 m_dialogClosed = true; 00617 } 00618 00619 void KFind::displayFinalDialog() const 00620 { 00621 TQString message; 00622 if ( numMatches() ) 00623 message = i18n( "1 match found.", "%n matches found.", numMatches() ); 00624 else 00625 message = i18n("<qt>No matches found for '<b>%1</b>'.</qt>").arg(TQStyleSheet::escape(m_pattern)); 00626 KMessageBox::information(dialogsParent(), message); 00627 } 00628 00629 bool KFind::shouldRestart( bool forceAsking, bool showNumMatches ) const 00630 { 00631 // Only ask if we did a "find from cursor", otherwise it's pointless. 00632 // Well, unless the user can modify the document during a search operation, 00633 // hence the force boolean. 00634 if ( !forceAsking && (m_options & KFindDialog::FromCursor) == 0 ) 00635 { 00636 displayFinalDialog(); 00637 return false; 00638 } 00639 TQString message; 00640 if ( showNumMatches ) 00641 { 00642 if ( numMatches() ) 00643 message = i18n( "1 match found.", "%n matches found.", numMatches() ); 00644 else 00645 message = i18n("No matches found for '<b>%1</b>'.").arg(TQStyleSheet::escape(m_pattern)); 00646 } 00647 else 00648 { 00649 if ( m_options & KFindDialog::FindBackwards ) 00650 message = i18n( "Beginning of document reached." ); 00651 else 00652 message = i18n( "End of document reached." ); 00653 } 00654 00655 message += "<br><br>"; // can't be in the i18n() of the first if() because of the plural form. 00656 // Hope this word puzzle is ok, it's a different sentence 00657 message += 00658 ( m_options & KFindDialog::FindBackwards ) ? 00659 i18n("Continue from the end?") 00660 : i18n("Continue from the beginning?"); 00661 00662 int ret = KMessageBox::questionYesNo( dialogsParent(), TQString("<qt>")+message+TQString("</qt>"), 00663 TQString::null, KStdGuiItem::cont(), KStdGuiItem::stop() ); 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 TQRegExp(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 TQString& 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 TQWidget* 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 ? (TQWidget*)d->findDialog : ( m_dialog ? m_dialog : parentWidget() ); 00708 } 00709 00710 #include "kfind.moc"