1/*
2 This file is part of the KDE project
3 SPDX-FileCopyrightText: 2001 S .R.Haque <srhaque@iee.org>.
4 SPDX-FileCopyrightText: 2002 David Faure <david@mandrakesoft.com>
5 SPDX-FileCopyrightText: 2004 Arend van Beelen jr. <arend@auton.nl>
6
7 SPDX-License-Identifier: LGPL-2.0-only
8*/
9
10#include "kfind.h"
11#include "kfind_p.h"
12
13#include "kfinddialog.h"
14
15#include <KGuiItem>
16#include <KLocalizedString>
17#include <KMessageBox>
18
19#include <QDialog>
20#include <QDialogButtonBox>
21#include <QHash>
22#include <QLabel>
23#include <QPushButton>
24#include <QRegularExpression>
25#include <QVBoxLayout>
26
27// #define DEBUG_FIND
28
29static const int INDEX_NOMATCH = -1;
30
31class KFindNextDialog : public QDialog
32{
33 Q_OBJECT
34public:
35 explicit KFindNextDialog(const QString &pattern, QWidget *parent);
36
37 QPushButton *findButton() const;
38
39private:
40 QPushButton *m_findButton = nullptr;
41};
42
43// Create the dialog.
44KFindNextDialog::KFindNextDialog(const QString &pattern, QWidget *parent)
45 : QDialog(parent)
46{
47 setModal(false);
48 setWindowTitle(i18n("Find Next"));
49
50 QVBoxLayout *layout = new QVBoxLayout(this);
51
52 layout->addWidget(new QLabel(i18n("<qt>Find next occurrence of '<b>%1</b>'?</qt>", pattern), this));
53
54 m_findButton = new QPushButton;
55 KGuiItem::assign(button: m_findButton, item: KStandardGuiItem::find());
56 m_findButton->setDefault(true);
57
58 QDialogButtonBox *buttonBox = new QDialogButtonBox(this);
59 buttonBox->addButton(button: m_findButton, role: QDialogButtonBox::ActionRole);
60 buttonBox->setStandardButtons(QDialogButtonBox::Close);
61 layout->addWidget(buttonBox);
62
63 connect(sender: buttonBox, signal: &QDialogButtonBox::accepted, context: this, slot: &QDialog::accept);
64 connect(sender: buttonBox, signal: &QDialogButtonBox::rejected, context: this, slot: &QDialog::reject);
65}
66
67QPushButton *KFindNextDialog::findButton() const
68{
69 return m_findButton;
70}
71
72////
73
74KFind::KFind(const QString &pattern, long options, QWidget *parent)
75 : KFind(*new KFindPrivate(this), pattern, options, parent)
76{
77}
78
79KFind::KFind(KFindPrivate &dd, const QString &pattern, long options, QWidget *parent)
80 : QObject(parent)
81 , d_ptr(&dd)
82{
83 Q_D(KFind);
84
85 d->options = options;
86 d->init(pattern);
87}
88
89KFind::KFind(const QString &pattern, long options, QWidget *parent, QWidget *findDialog)
90 : KFind(*new KFindPrivate(this), pattern, options, parent, findDialog)
91{
92}
93
94KFind::KFind(KFindPrivate &dd, const QString &pattern, long options, QWidget *parent, QWidget *findDialog)
95 : QObject(parent)
96 , d_ptr(&dd)
97{
98 Q_D(KFind);
99
100 d->findDialog = findDialog;
101 d->options = options;
102 d->init(pattern);
103}
104
105void KFindPrivate::init(const QString &_pattern)
106{
107 Q_Q(KFind);
108
109 matches = 0;
110 pattern = _pattern;
111 dialog = nullptr;
112 dialogClosed = false;
113 index = INDEX_NOMATCH;
114 lastResult = KFind::NoMatch;
115
116 // TODO: KF6 change this comment once d->regExp is removed
117 // set options and create d->regExp with the right options
118 q->setOptions(options);
119}
120
121KFind::~KFind() = default;
122
123bool KFind::needData() const
124{
125 Q_D(const KFind);
126
127 // always true when d->text is empty.
128 if (d->options & KFind::FindBackwards)
129 // d->index==-1 and d->lastResult==Match means we haven't answered nomatch yet
130 // This is important in the "replace with a prompt" case.
131 {
132 return (d->index < 0 && d->lastResult != Match);
133 } else
134 // "index over length" test removed: we want to get a nomatch before we set data again
135 // This is important in the "replace with a prompt" case.
136 {
137 return d->index == INDEX_NOMATCH;
138 }
139}
140
141void KFind::setData(const QString &data, int startPos)
142{
143 setData(id: -1, data, startPos);
144}
145
146void KFind::setData(int id, const QString &data, int startPos)
147{
148 Q_D(KFind);
149
150 // cache the data for incremental find
151 if (d->options & KFind::FindIncremental) {
152 if (id != -1) {
153 d->customIds = true;
154 } else {
155 id = d->currentId + 1;
156 }
157
158 Q_ASSERT(id <= d->data.size());
159
160 if (id == d->data.size()) {
161 d->data.append(t: KFindPrivate::Data(id, data, true));
162 } else {
163 d->data.replace(i: id, t: KFindPrivate::Data(id, data, true));
164 }
165 Q_ASSERT(d->data.at(id).text == data);
166 }
167
168 if (!(d->options & KFind::FindIncremental) || needData()) {
169 d->text = data;
170
171 if (startPos != -1) {
172 d->index = startPos;
173 } else if (d->options & KFind::FindBackwards) {
174 d->index = d->text.length();
175 } else {
176 d->index = 0;
177 }
178#ifdef DEBUG_FIND
179 // qDebug() << "setData: '" << d->text << "' d->index=" << d->index;
180#endif
181 Q_ASSERT(d->index != INDEX_NOMATCH);
182 d->lastResult = NoMatch;
183
184 d->currentId = id;
185 }
186}
187
188QDialog *KFind::findNextDialog(bool create)
189{
190 Q_D(KFind);
191
192 if (!d->dialog && create) {
193 KFindNextDialog *dialog = new KFindNextDialog(d->pattern, parentWidget());
194 connect(sender: dialog->findButton(), signal: &QPushButton::clicked, context: this, slot: [d]() {
195 d->slotFindNext();
196 });
197 connect(sender: dialog, signal: &QDialog::finished, context: this, slot: [d]() {
198 d->slotDialogClosed();
199 });
200 d->dialog = dialog;
201 }
202 return d->dialog;
203}
204
205KFind::Result KFind::find()
206{
207 Q_D(KFind);
208
209 Q_ASSERT(d->index != INDEX_NOMATCH || d->patternChanged);
210
211 if (d->lastResult == Match && !d->patternChanged) {
212 // Move on before looking for the next match, _if_ we just found a match
213 if (d->options & KFind::FindBackwards) {
214 d->index--;
215 if (d->index == -1) { // don't call KFind::find with -1, it has a special meaning
216 d->lastResult = NoMatch;
217 return NoMatch;
218 }
219 } else {
220 d->index++;
221 }
222 }
223 d->patternChanged = false;
224
225 if (d->options & KFind::FindIncremental) {
226 // if the current pattern is shorter than the matchedPattern we can
227 // probably look up the match in the incrementalPath
228 if (d->pattern.length() < d->matchedPattern.length()) {
229 KFindPrivate::Match match;
230 if (!d->pattern.isEmpty()) {
231 match = d->incrementalPath.value(key: d->pattern);
232 } else if (d->emptyMatch) {
233 match = *d->emptyMatch;
234 }
235 QString previousPattern(d->matchedPattern);
236 d->matchedPattern = d->pattern;
237 if (!match.isNull()) {
238 bool clean = true;
239
240 // find the first result backwards on the path that isn't dirty
241 while (d->data.at(i: match.dataId).dirty == true && !d->pattern.isEmpty()) {
242 d->pattern.truncate(pos: d->pattern.length() - 1);
243
244 match = d->incrementalPath.value(key: d->pattern);
245
246 clean = false;
247 }
248
249 // remove all matches that lie after the current match
250 while (d->pattern.length() < previousPattern.length()) {
251 d->incrementalPath.remove(key: previousPattern);
252 previousPattern.truncate(pos: previousPattern.length() - 1);
253 }
254
255 // set the current text, index, etc. to the found match
256 d->text = d->data.at(i: match.dataId).text;
257 d->index = match.index;
258 d->matchedLength = match.matchedLength;
259 d->currentId = match.dataId;
260
261 // if the result is clean we can return it now
262 if (clean) {
263 if (d->customIds) {
264 Q_EMIT textFoundAtId(id: d->currentId, matchingIndex: d->index, matchedLength: d->matchedLength);
265 } else {
266 Q_EMIT textFound(text: d->text, matchingIndex: d->index, matchedLength: d->matchedLength);
267 }
268
269 d->lastResult = Match;
270 d->matchedPattern = d->pattern;
271 return Match;
272 }
273 }
274 // if we couldn't look up the match, the new pattern isn't a
275 // substring of the matchedPattern, so we start a new search
276 else {
277 d->startNewIncrementalSearch();
278 }
279 }
280 // if the new pattern is longer than the matchedPattern we might be
281 // able to proceed from the last search
282 else if (d->pattern.length() > d->matchedPattern.length()) {
283 // continue from the previous pattern
284 if (d->pattern.startsWith(s: d->matchedPattern)) {
285 // we can't proceed from the previous position if the previous
286 // position already failed
287 if (d->index == INDEX_NOMATCH) {
288 return NoMatch;
289 }
290
291 QString temp(d->pattern);
292 d->pattern.truncate(pos: d->matchedPattern.length() + 1);
293 d->matchedPattern = temp;
294 }
295 // start a new search
296 else {
297 d->startNewIncrementalSearch();
298 }
299 }
300 // if the new pattern is as long as the matchedPattern, we reset if
301 // they are not equal
302 else if (d->pattern != d->matchedPattern) {
303 d->startNewIncrementalSearch();
304 }
305 }
306
307#ifdef DEBUG_FIND
308 // qDebug() << "d->index=" << d->index;
309#endif
310 do {
311 // if we have multiple data blocks in our cache, walk through these
312 // blocks till we either searched all blocks or we find a match
313 do {
314 // Find the next candidate match.
315 d->index = KFind::find(text: d->text, pattern: d->pattern, index: d->index, options: d->options, matchedLength: &d->matchedLength, rmatch: nullptr);
316
317 if (d->options & KFind::FindIncremental) {
318 d->data[d->currentId].dirty = false;
319 }
320
321 if (d->index == -1 && d->currentId < d->data.count() - 1) {
322 d->text = d->data.at(i: ++d->currentId).text;
323
324 if (d->options & KFind::FindBackwards) {
325 d->index = d->text.length();
326 } else {
327 d->index = 0;
328 }
329 } else {
330 break;
331 }
332 } while (!(d->options & KFind::RegularExpression));
333
334 if (d->index != -1) {
335 // Flexibility: the app can add more rules to validate a possible match
336 if (validateMatch(text: d->text, index: d->index, matchedlength: d->matchedLength)) {
337 bool done = true;
338
339 if (d->options & KFind::FindIncremental) {
340 if (d->pattern.isEmpty()) {
341 delete d->emptyMatch;
342 d->emptyMatch = new KFindPrivate::Match(d->currentId, d->index, d->matchedLength);
343 } else {
344 d->incrementalPath.insert(key: d->pattern, value: KFindPrivate::Match(d->currentId, d->index, d->matchedLength));
345 }
346
347 if (d->pattern.length() < d->matchedPattern.length()) {
348 d->pattern += QStringView(d->matchedPattern).mid(pos: d->pattern.length(), n: 1);
349 done = false;
350 }
351 }
352
353 if (done) {
354 d->matches++;
355 // Tell the world about the match we found, in case someone wants to
356 // highlight it.
357 if (d->customIds) {
358 Q_EMIT textFoundAtId(id: d->currentId, matchingIndex: d->index, matchedLength: d->matchedLength);
359 } else {
360 Q_EMIT textFound(text: d->text, matchingIndex: d->index, matchedLength: d->matchedLength);
361 }
362
363 if (!d->dialogClosed) {
364 findNextDialog(create: true)->show();
365 }
366
367#ifdef DEBUG_FIND
368 // qDebug() << "Match. Next d->index=" << d->index;
369#endif
370 d->lastResult = Match;
371 return Match;
372 }
373 } else { // Skip match
374 if (d->options & KFind::FindBackwards) {
375 d->index--;
376 } else {
377 d->index++;
378 }
379 }
380 } else {
381 if (d->options & KFind::FindIncremental) {
382 QString temp(d->pattern);
383 temp.truncate(pos: temp.length() - 1);
384 d->pattern = d->matchedPattern;
385 d->matchedPattern = temp;
386 }
387
388 d->index = INDEX_NOMATCH;
389 }
390 } while (d->index != INDEX_NOMATCH);
391
392#ifdef DEBUG_FIND
393 // qDebug() << "NoMatch. d->index=" << d->index;
394#endif
395 d->lastResult = NoMatch;
396 return NoMatch;
397}
398
399void KFindPrivate::startNewIncrementalSearch()
400{
401 KFindPrivate::Match *match = emptyMatch;
402 if (match == nullptr) {
403 text.clear();
404 index = 0;
405 currentId = 0;
406 } else {
407 text = data.at(i: match->dataId).text;
408 index = match->index;
409 currentId = match->dataId;
410 }
411 matchedLength = 0;
412 incrementalPath.clear();
413 delete emptyMatch;
414 emptyMatch = nullptr;
415 matchedPattern = pattern;
416 pattern.clear();
417}
418
419static bool isInWord(QChar ch)
420{
421 return ch.isLetter() || ch.isDigit() || ch == QLatin1Char('_');
422}
423
424static bool isWholeWords(const QString &text, int starts, int matchedLength)
425{
426 if (starts == 0 || !isInWord(ch: text.at(i: starts - 1))) {
427 const int ends = starts + matchedLength;
428 if (ends == text.length() || !isInWord(ch: text.at(i: ends))) {
429 return true;
430 }
431 }
432 return false;
433}
434
435static bool matchOk(const QString &text, int index, int matchedLength, long options)
436{
437 if (options & KFind::WholeWordsOnly) {
438 // Is the match delimited correctly?
439 if (isWholeWords(text, starts: index, matchedLength)) {
440 return true;
441 }
442 } else {
443 // Non-whole-word search: this match is good
444 return true;
445 }
446 return false;
447}
448
449static int findRegex(const QString &text, const QString &pattern, int index, long options, int *matchedLength, QRegularExpressionMatch *rmatch)
450{
451 QString _pattern = pattern;
452
453 // Always enable Unicode support in QRegularExpression
454 QRegularExpression::PatternOptions opts = QRegularExpression::UseUnicodePropertiesOption;
455 // instead of this rudimentary test, add a checkbox to toggle MultilineOption ?
456 if (pattern.startsWith(c: QLatin1Char('^')) || pattern.endsWith(c: QLatin1Char('$'))) {
457 opts |= QRegularExpression::MultilineOption;
458 } else if (options & KFind::WholeWordsOnly) { // WholeWordsOnly makes no sense with multiline
459 _pattern = QLatin1String("\\b") + pattern + QLatin1String("\\b");
460 }
461
462 if (!(options & KFind::CaseSensitive)) {
463 opts |= QRegularExpression::CaseInsensitiveOption;
464 }
465
466 QRegularExpression re(_pattern, opts);
467 QRegularExpressionMatch match;
468 if (options & KFind::FindBackwards) {
469 // Backward search, until the beginning of the line...
470 (void)text.lastIndexOf(re, from: index, rmatch: &match);
471 } else {
472 // Forward search, until the end of the line...
473 match = re.match(subject: text, offset: index);
474 }
475
476 // index is -1 if no match is found
477 index = match.capturedStart(nth: 0);
478 // matchedLength is 0 if no match is found
479 *matchedLength = match.capturedLength(nth: 0);
480
481 if (rmatch) {
482 *rmatch = match;
483 }
484
485 return index;
486}
487
488// static
489int KFind::find(const QString &text, const QString &pattern, int index, long options, int *matchedLength, QRegularExpressionMatch *rmatch)
490{
491 // Handle regular expressions in the appropriate way.
492 if (options & KFind::RegularExpression) {
493 return findRegex(text, pattern, index, options, matchedLength, rmatch);
494 }
495
496 // In Qt4 QString("aaaaaa").lastIndexOf("a",6) returns -1; we need
497 // to start at text.length() - pattern.length() to give a valid index to QString.
498 if (options & KFind::FindBackwards) {
499 index = qMin(a: qMax(a: 0, b: text.length() - pattern.length()), b: index);
500 }
501
502 Qt::CaseSensitivity caseSensitive = (options & KFind::CaseSensitive) ? Qt::CaseSensitive : Qt::CaseInsensitive;
503
504 if (options & KFind::FindBackwards) {
505 // Backward search, until the beginning of the line...
506 while (index >= 0) {
507 // ...find the next match.
508 index = text.lastIndexOf(s: pattern, from: index, cs: caseSensitive);
509 if (index == -1) {
510 break;
511 }
512
513 if (matchOk(text, index, matchedLength: pattern.length(), options)) {
514 break;
515 }
516 index--;
517 // qDebug() << "decrementing:" << index;
518 }
519 } else {
520 // Forward search, until the end of the line...
521 while (index <= text.length()) {
522 // ...find the next match.
523 index = text.indexOf(s: pattern, from: index, cs: caseSensitive);
524 if (index == -1) {
525 break;
526 }
527
528 if (matchOk(text, index, matchedLength: pattern.length(), options)) {
529 break;
530 }
531 index++;
532 }
533 if (index > text.length()) { // end of line
534 // qDebug() << "at" << index << "-> not found";
535 index = -1; // not found
536 }
537 }
538 if (index <= -1) {
539 *matchedLength = 0;
540 } else {
541 *matchedLength = pattern.length();
542 }
543 return index;
544}
545
546void KFindPrivate::slotFindNext()
547{
548 Q_Q(KFind);
549
550 Q_EMIT q->findNext();
551}
552
553void KFindPrivate::slotDialogClosed()
554{
555 Q_Q(KFind);
556
557#ifdef DEBUG_FIND
558 // qDebug() << " Begin";
559#endif
560 Q_EMIT q->dialogClosed();
561 dialogClosed = true;
562#ifdef DEBUG_FIND
563 // qDebug() << " End";
564#endif
565}
566
567void KFind::displayFinalDialog() const
568{
569 Q_D(const KFind);
570
571 QString message;
572 if (numMatches()) {
573 message = i18np("1 match found.", "%1 matches found.", numMatches());
574 } else {
575 message = i18n("<qt>No matches found for '<b>%1</b>'.</qt>", d->pattern.toHtmlEscaped());
576 }
577 KMessageBox::information(parent: dialogsParent(), text: message);
578}
579
580bool KFind::shouldRestart(bool forceAsking, bool showNumMatches) const
581{
582 Q_D(const KFind);
583
584 // Only ask if we did a "find from cursor", otherwise it's pointless.
585 // Well, unless the user can modify the document during a search operation,
586 // hence the force boolean.
587 if (!forceAsking && (d->options & KFind::FromCursor) == 0) {
588 displayFinalDialog();
589 return false;
590 }
591 QString message;
592 if (showNumMatches) {
593 if (numMatches()) {
594 message = i18np("1 match found.", "%1 matches found.", numMatches());
595 } else {
596 message = i18n("No matches found for '<b>%1</b>'.", d->pattern.toHtmlEscaped());
597 }
598 } else {
599 if (d->options & KFind::FindBackwards) {
600 message = i18n("Beginning of document reached.");
601 } else {
602 message = i18n("End of document reached.");
603 }
604 }
605
606 message += QLatin1String("<br><br>"); // can't be in the i18n() of the first if() because of the plural form.
607 // Hope this word puzzle is ok, it's a different sentence
608 message += (d->options & KFind::FindBackwards) ? i18n("Continue from the end?") : i18n("Continue from the beginning?");
609
610 int ret = KMessageBox::questionTwoActions(parent: dialogsParent(),
611 QStringLiteral("<qt>%1</qt>").arg(a: message),
612 title: QString(),
613 primaryAction: KStandardGuiItem::cont(),
614 secondaryAction: KStandardGuiItem::stop());
615 bool yes = (ret == KMessageBox::PrimaryAction);
616 if (yes) {
617 const_cast<KFindPrivate *>(d)->options &= ~KFind::FromCursor; // clear FromCursor option
618 }
619 return yes;
620}
621
622long KFind::options() const
623{
624 Q_D(const KFind);
625
626 return d->options;
627}
628
629void KFind::setOptions(long options)
630{
631 Q_D(KFind);
632
633 d->options = options;
634}
635
636void KFind::closeFindNextDialog()
637{
638 Q_D(KFind);
639
640 if (d->dialog) {
641 d->dialog->deleteLater();
642 d->dialog = nullptr;
643 }
644 d->dialogClosed = true;
645}
646
647int KFind::index() const
648{
649 Q_D(const KFind);
650
651 return d->index;
652}
653
654QString KFind::pattern() const
655{
656 Q_D(const KFind);
657
658 return d->pattern;
659}
660
661void KFind::setPattern(const QString &pattern)
662{
663 Q_D(KFind);
664
665 if (d->pattern != pattern) {
666 d->patternChanged = true;
667 d->matches = 0;
668 }
669
670 d->pattern = pattern;
671
672 // TODO: KF6 change this comment once d->regExp is removed
673 // set the options and rebuild d->regeExp if necessary
674 setOptions(options());
675}
676
677int KFind::numMatches() const
678{
679 Q_D(const KFind);
680
681 return d->matches;
682}
683
684void KFind::resetCounts()
685{
686 Q_D(KFind);
687
688 d->matches = 0;
689}
690
691bool KFind::validateMatch(const QString &, int, int)
692{
693 return true;
694}
695
696QWidget *KFind::parentWidget() const
697{
698 return static_cast<QWidget *>(parent());
699}
700
701QWidget *KFind::dialogsParent() const
702{
703 Q_D(const KFind);
704
705 // If the find dialog is still up, it should get the focus when closing a message box
706 // Otherwise, maybe the "find next?" dialog is up
707 // Otherwise, the "view" is the parent.
708 return d->findDialog ? static_cast<QWidget *>(d->findDialog) : (d->dialog ? d->dialog : parentWidget());
709}
710
711#include "kfind.moc"
712#include "moc_kfind.cpp"
713

source code of ktextwidgets/src/findreplace/kfind.cpp