File indexing completed on 2024-05-05 14:20:13
0001 /* 0002 SPDX-FileCopyrightText: 2001-2009 Otto Bruggeman <bruggie@gmail.com> 0003 SPDX-FileCopyrightText: 2001-2003 John Firebaugh <jfirebaugh@kde.org> 0004 0005 SPDX-License-Identifier: GPL-2.0-or-later 0006 */ 0007 0008 #include "diffmodel.h" 0009 0010 #include <komparediffdebug.h> 0011 #include "difference.h" 0012 #include "levenshteintable.h" 0013 #include "stringlistpair.h" 0014 #include "parserbase.h" 0015 0016 using namespace Diff2; 0017 0018 /** */ 0019 DiffModel::DiffModel(const QString& source, const QString& destination) : 0020 m_source(source), 0021 m_destination(destination), 0022 m_sourcePath(), 0023 m_destinationPath(), 0024 m_sourceFile(), 0025 m_destinationFile(), 0026 m_sourceTimestamp(), 0027 m_destinationTimestamp(), 0028 m_sourceRevision(), 0029 m_destinationRevision(), 0030 m_appliedCount(0), 0031 m_diffIndex(0), 0032 m_selectedDifference(nullptr), 0033 m_blended(false) 0034 { 0035 splitSourceInPathAndFileName(); 0036 splitDestinationInPathAndFileName(); 0037 } 0038 0039 DiffModel::DiffModel() : 0040 m_source(), 0041 m_destination(), 0042 m_sourcePath(), 0043 m_destinationPath(), 0044 m_sourceFile(), 0045 m_destinationFile(), 0046 m_sourceTimestamp(), 0047 m_destinationTimestamp(), 0048 m_sourceRevision(), 0049 m_destinationRevision(), 0050 m_appliedCount(0), 0051 m_diffIndex(0), 0052 m_selectedDifference(nullptr), 0053 m_blended(false) 0054 { 0055 } 0056 0057 /** */ 0058 DiffModel::~DiffModel() 0059 { 0060 m_selectedDifference = nullptr; 0061 0062 qDeleteAll(m_hunks); 0063 qDeleteAll(m_differences); 0064 } 0065 0066 void DiffModel::splitSourceInPathAndFileName() 0067 { 0068 int pos; 0069 0070 if ((pos = m_source.lastIndexOf(QLatin1Char('/'))) >= 0) 0071 m_sourcePath = m_source.mid(0, pos + 1); 0072 0073 if ((pos = m_source.lastIndexOf(QLatin1Char('/'))) >= 0) 0074 m_sourceFile = m_source.mid(pos + 1, m_source.length() - pos); 0075 else 0076 m_sourceFile = m_source; 0077 0078 qCDebug(LIBKOMPAREDIFF2) << m_source << " was split into " << m_sourcePath << " and " << m_sourceFile; 0079 } 0080 0081 void DiffModel::splitDestinationInPathAndFileName() 0082 { 0083 int pos; 0084 0085 if ((pos = m_destination.lastIndexOf(QLatin1Char('/'))) >= 0) 0086 m_destinationPath = m_destination.mid(0, pos + 1); 0087 0088 if ((pos = m_destination.lastIndexOf(QLatin1Char('/'))) >= 0) 0089 m_destinationFile = m_destination.mid(pos + 1, m_destination.length() - pos); 0090 else 0091 m_destinationFile = m_destination; 0092 0093 qCDebug(LIBKOMPAREDIFF2) << m_destination << " was split into " << m_destinationPath << " and " << m_destinationFile; 0094 } 0095 0096 DiffModel& DiffModel::operator=(const DiffModel& model) 0097 { 0098 if (&model != this) // Guard from self-assignment 0099 { 0100 m_source = model.m_source; 0101 m_destination = model.m_destination; 0102 m_sourcePath = model.m_sourcePath; 0103 m_sourceFile = model.m_sourceFile; 0104 m_sourceTimestamp = model.m_sourceTimestamp; 0105 m_sourceRevision = model.m_sourceRevision; 0106 m_destinationPath = model.m_destinationPath; 0107 m_destinationFile = model.m_destinationFile; 0108 m_destinationTimestamp = model.m_destinationTimestamp; 0109 m_destinationRevision = model.m_destinationRevision; 0110 m_appliedCount = model.m_appliedCount; 0111 0112 m_diffIndex = model.m_diffIndex; 0113 m_selectedDifference = model.m_selectedDifference; 0114 } 0115 0116 return *this; 0117 } 0118 0119 bool DiffModel::operator<(const DiffModel& model) 0120 { 0121 if (localeAwareCompareSource(model) < 0) 0122 return true; 0123 return false; 0124 } 0125 0126 int DiffModel::localeAwareCompareSource(const DiffModel& model) 0127 { 0128 qCDebug(LIBKOMPAREDIFF2) << "Path: " << model.m_sourcePath; 0129 qCDebug(LIBKOMPAREDIFF2) << "File: " << model.m_sourceFile; 0130 0131 int result = m_sourcePath.localeAwareCompare(model.m_sourcePath); 0132 0133 if (result == 0) 0134 return m_sourceFile.localeAwareCompare(model.m_sourceFile); 0135 0136 return result; 0137 } 0138 0139 QString DiffModel::recreateDiff() const 0140 { 0141 // For now we'll always return a diff in the diff format 0142 QString diff; 0143 0144 // recreate header 0145 const QChar tab = QLatin1Char('\t'); 0146 const QChar nl = QLatin1Char('\n'); 0147 diff += QStringLiteral("--- %1\t%2").arg(ParserBase::escapePath(m_source), m_sourceTimestamp); 0148 if (!m_sourceRevision.isEmpty()) 0149 diff += tab + m_sourceRevision; 0150 diff += nl; 0151 diff += QStringLiteral("+++ %1\t%2").arg(ParserBase::escapePath(m_destination), m_destinationTimestamp); 0152 if (!m_destinationRevision.isEmpty()) 0153 diff += tab + m_destinationRevision; 0154 diff += nl; 0155 0156 // recreate body by iterating over the hunks 0157 DiffHunkListConstIterator hunkIt = m_hunks.begin(); 0158 DiffHunkListConstIterator hEnd = m_hunks.end(); 0159 0160 for (; hunkIt != hEnd; ++hunkIt) 0161 { 0162 if ((*hunkIt)->type() != DiffHunk::AddedByBlend) 0163 diff += (*hunkIt)->recreateHunk(); 0164 } 0165 0166 return diff; 0167 } 0168 0169 Difference* DiffModel::firstDifference() 0170 { 0171 qCDebug(LIBKOMPAREDIFF2) << "DiffModel::firstDifference()"; 0172 m_diffIndex = 0; 0173 qCDebug(LIBKOMPAREDIFF2) << "m_diffIndex = " << m_diffIndex; 0174 0175 m_selectedDifference = m_differences[ m_diffIndex ]; 0176 0177 return m_selectedDifference; 0178 } 0179 0180 Difference* DiffModel::lastDifference() 0181 { 0182 qCDebug(LIBKOMPAREDIFF2) << "DiffModel::lastDifference()"; 0183 m_diffIndex = m_differences.count() - 1; 0184 qCDebug(LIBKOMPAREDIFF2) << "m_diffIndex = " << m_diffIndex; 0185 0186 m_selectedDifference = m_differences[ m_diffIndex ]; 0187 0188 return m_selectedDifference; 0189 } 0190 0191 Difference* DiffModel::prevDifference() 0192 { 0193 qCDebug(LIBKOMPAREDIFF2) << "DiffModel::prevDifference()"; 0194 if (m_diffIndex > 0 && --m_diffIndex < m_differences.count()) 0195 { 0196 qCDebug(LIBKOMPAREDIFF2) << "m_diffIndex = " << m_diffIndex; 0197 m_selectedDifference = m_differences[ m_diffIndex ]; 0198 } 0199 else 0200 { 0201 m_selectedDifference = nullptr; 0202 m_diffIndex = 0; 0203 qCDebug(LIBKOMPAREDIFF2) << "m_diffIndex = " << m_diffIndex; 0204 } 0205 0206 return m_selectedDifference; 0207 } 0208 0209 Difference* DiffModel::nextDifference() 0210 { 0211 qCDebug(LIBKOMPAREDIFF2) << "DiffModel::nextDifference()"; 0212 if (++m_diffIndex < m_differences.count()) 0213 { 0214 qCDebug(LIBKOMPAREDIFF2) << "m_diffIndex = " << m_diffIndex; 0215 m_selectedDifference = m_differences[ m_diffIndex ]; 0216 } 0217 else 0218 { 0219 m_selectedDifference = nullptr; 0220 m_diffIndex = 0; // just for safety... 0221 qCDebug(LIBKOMPAREDIFF2) << "m_diffIndex = " << m_diffIndex; 0222 } 0223 0224 return m_selectedDifference; 0225 } 0226 0227 const QString DiffModel::sourceFile() const 0228 { 0229 return m_sourceFile; 0230 } 0231 0232 const QString DiffModel::destinationFile() const 0233 { 0234 return m_destinationFile; 0235 } 0236 0237 const QString DiffModel::sourcePath() const 0238 { 0239 return m_sourcePath; 0240 } 0241 0242 const QString DiffModel::destinationPath() const 0243 { 0244 return m_destinationPath; 0245 } 0246 0247 void DiffModel::setSourceFile(QString path) 0248 { 0249 m_source = path; 0250 splitSourceInPathAndFileName(); 0251 } 0252 0253 void DiffModel::setDestinationFile(QString path) 0254 { 0255 m_destination = path; 0256 splitDestinationInPathAndFileName(); 0257 } 0258 0259 void DiffModel::setSourceTimestamp(QString timestamp) 0260 { 0261 m_sourceTimestamp = timestamp; 0262 } 0263 0264 void DiffModel::setDestinationTimestamp(QString timestamp) 0265 { 0266 m_destinationTimestamp = timestamp; 0267 } 0268 0269 void DiffModel::setSourceRevision(QString revision) 0270 { 0271 m_sourceRevision = revision; 0272 } 0273 0274 void DiffModel::setDestinationRevision(QString revision) 0275 { 0276 m_destinationRevision = revision; 0277 } 0278 0279 void DiffModel::addHunk(DiffHunk* hunk) 0280 { 0281 m_hunks.append(hunk); 0282 } 0283 0284 void DiffModel::addDiff(Difference* diff) 0285 { 0286 m_differences.append(diff); 0287 connect(diff, &Difference::differenceApplied, 0288 this, &DiffModel::slotDifferenceApplied); 0289 } 0290 0291 bool DiffModel::hasUnsavedChanges(void) const 0292 { 0293 DifferenceListConstIterator diffIt = m_differences.begin(); 0294 DifferenceListConstIterator endIt = m_differences.end(); 0295 0296 for (; diffIt != endIt; ++diffIt) 0297 { 0298 if ((*diffIt)->isUnsaved()) 0299 return true; 0300 } 0301 0302 return false; 0303 } 0304 0305 void DiffModel::applyDifference(bool apply) 0306 { 0307 bool appliedState = m_selectedDifference->applied(); 0308 if (appliedState == apply) 0309 { 0310 return; 0311 } 0312 if (apply && !m_selectedDifference->applied()) 0313 ++m_appliedCount; 0314 else if (!apply && m_selectedDifference->applied()) 0315 --m_appliedCount; 0316 0317 m_selectedDifference->apply(apply); 0318 } 0319 0320 static int GetDifferenceDelta(Difference* diff) 0321 { 0322 int delta = diff->destinationLineCount() - diff->sourceLineCount(); 0323 if (!diff->applied()) 0324 { 0325 delta = -delta; 0326 } 0327 return delta; 0328 } 0329 0330 void DiffModel::slotDifferenceApplied(Difference* diff) 0331 { 0332 int delta = GetDifferenceDelta(diff); 0333 for (Difference *current : std::as_const(m_differences)) { 0334 if (current->destinationLineNumber() > diff->destinationLineNumber()) 0335 { 0336 current->setTrackingDestinationLineNumber(current->trackingDestinationLineNumber() + delta); 0337 } 0338 } 0339 } 0340 0341 void DiffModel::applyAllDifferences(bool apply) 0342 { 0343 if (apply) 0344 { 0345 m_appliedCount = m_differences.count(); 0346 } 0347 else 0348 { 0349 m_appliedCount = 0; 0350 } 0351 0352 DifferenceListIterator diffIt = m_differences.begin(); 0353 DifferenceListIterator dEnd = m_differences.end(); 0354 0355 int totalDelta = 0; 0356 for (; diffIt != dEnd; ++diffIt) 0357 { 0358 (*diffIt)->setTrackingDestinationLineNumber((*diffIt)->trackingDestinationLineNumber() + totalDelta); 0359 bool appliedState = (*diffIt)->applied(); 0360 if (appliedState == apply) 0361 { 0362 continue; 0363 } 0364 (*diffIt)->applyQuietly(apply); 0365 int currentDelta = GetDifferenceDelta(*diffIt); 0366 totalDelta += currentDelta; 0367 } 0368 } 0369 0370 bool DiffModel::setSelectedDifference(Difference* diff) 0371 { 0372 qCDebug(LIBKOMPAREDIFF2) << "diff = " << diff; 0373 qCDebug(LIBKOMPAREDIFF2) << "m_selectedDifference = " << m_selectedDifference; 0374 0375 if (diff != m_selectedDifference) 0376 { 0377 if ((m_differences.indexOf(diff)) == -1) 0378 return false; 0379 // Do not set m_diffIndex if it cant be found 0380 m_diffIndex = m_differences.indexOf(diff); 0381 qCDebug(LIBKOMPAREDIFF2) << "m_diffIndex = " << m_diffIndex; 0382 m_selectedDifference = diff; 0383 } 0384 0385 return true; 0386 } 0387 0388 QPair<QList<Difference*>, QList<Difference*> > DiffModel::linesChanged(const QStringList& oldLines, const QStringList& newLines, int editLineNumber) 0389 { 0390 // These two will be returned as the function result 0391 QList<Difference*> inserted; 0392 QList<Difference*> removed; 0393 if (oldLines.size() == 0 && newLines.size() == 0) { 0394 return qMakePair(QList<Difference*>(), QList<Difference*>()); 0395 } 0396 int editLineEnd = editLineNumber + oldLines.size(); 0397 // Find the range of differences [iterBegin, iterEnd) that should be updated 0398 // TODO: assume that differences are ordered by starting line. Check that this is always the case 0399 DifferenceList applied; 0400 DifferenceListIterator iterBegin; // first diff ending a line before editLineNo or later 0401 for (iterBegin = m_differences.begin(); iterBegin != m_differences.end(); ++iterBegin) { 0402 // If the difference ends a line before the edit starts, they should be merged if this difference is applied. 0403 // Also it should be merged if it starts on editLineNumber, otherwise there will be two markers for the same line 0404 int lineAfterLast = (*iterBegin)->trackingDestinationLineEnd(); 0405 if (lineAfterLast > editLineNumber || (lineAfterLast == editLineNumber && 0406 ((*iterBegin)->applied() || (*iterBegin)->trackingDestinationLineNumber() == editLineNumber))) { 0407 break; 0408 } 0409 } 0410 DifferenceListIterator iterEnd; 0411 for (iterEnd = iterBegin; iterEnd != m_differences.end(); ++iterEnd) { 0412 // If the difference starts a line after the edit ends, it should still be merged if it is applied 0413 int firstLine = (*iterEnd)->trackingDestinationLineNumber(); 0414 if (firstLine > editLineEnd || (!(*iterEnd)->applied() && firstLine == editLineEnd)) { 0415 break; 0416 } 0417 if ((*iterEnd)->applied()) { 0418 applied.append(*iterEnd); 0419 } 0420 } 0421 0422 // Compute line numbers in source and destination to which the for diff line sequences (will be created later) 0423 int sourceLineNumber; 0424 int destinationLineNumber; 0425 if (iterBegin == m_differences.end()) { // All existing diffs are after the change 0426 destinationLineNumber = editLineNumber; 0427 if (!m_differences.isEmpty()) { 0428 sourceLineNumber = m_differences.last()->sourceLineEnd() - (m_differences.last()->trackingDestinationLineEnd() - editLineNumber); 0429 } else { 0430 sourceLineNumber = destinationLineNumber; 0431 } 0432 } else if (!(*iterBegin)->applied() || (*iterBegin)->trackingDestinationLineNumber() >= editLineNumber) { 0433 destinationLineNumber = editLineNumber; 0434 sourceLineNumber = (*iterBegin)->sourceLineNumber() - ((*iterBegin)->trackingDestinationLineNumber() - editLineNumber); 0435 } else { 0436 sourceLineNumber = (*iterBegin)->sourceLineNumber(); 0437 destinationLineNumber = (*iterBegin)->trackingDestinationLineNumber(); 0438 } 0439 0440 // Only the applied differences are of interest, unapplied can be safely removed 0441 DifferenceListConstIterator appliedBegin = applied.constBegin(); 0442 DifferenceListConstIterator appliedEnd = applied.constEnd(); 0443 0444 // Now create a sequence of lines for the destination file and the corresponding lines in source 0445 QStringList sourceLines; 0446 QStringList destinationLines; 0447 DifferenceListIterator insertPosition; // where to insert the created diffs 0448 if (appliedBegin == appliedEnd) { 0449 destinationLines = newLines; 0450 sourceLines = oldLines; 0451 } else { 0452 // Create the destination line sequence 0453 int firstDestinationLineNumber = (*appliedBegin)->trackingDestinationLineNumber(); 0454 for (int lineNumber = firstDestinationLineNumber; lineNumber < editLineNumber; ++lineNumber) { 0455 destinationLines.append((*appliedBegin)->destinationLineAt(lineNumber - firstDestinationLineNumber)->string()); 0456 } 0457 for (const QString& line : newLines) { 0458 destinationLines.append(line); 0459 } 0460 DifferenceListConstIterator appliedLast = appliedEnd; 0461 --appliedLast; 0462 int lastDestinationLineNumber = (*appliedLast)->trackingDestinationLineNumber(); 0463 for (int lineNumber = editLineEnd; lineNumber < (*appliedLast)->trackingDestinationLineEnd(); ++lineNumber) { 0464 destinationLines.append((*appliedLast)->destinationLineAt(lineNumber - lastDestinationLineNumber)->string()); 0465 } 0466 0467 // Create the source line sequence 0468 if ((*appliedBegin)->trackingDestinationLineNumber() >= editLineNumber) { 0469 for (int i = editLineNumber; i < (*appliedBegin)->trackingDestinationLineNumber(); ++i) { 0470 sourceLines.append(oldLines.at(i - editLineNumber)); 0471 } 0472 } 0473 0474 for (DifferenceListConstIterator iter = appliedBegin; iter != appliedEnd;) { 0475 int startPos = (*iter)->trackingDestinationLineNumber(); 0476 if ((*iter)->applied()) { 0477 for (int i = 0; i < (*iter)->sourceLineCount(); ++i) { 0478 sourceLines.append((*iter)->sourceLineAt(i)->string()); 0479 } 0480 startPos = (*iter)->trackingDestinationLineEnd(); 0481 } else if (startPos < editLineNumber) { 0482 startPos = editLineNumber; 0483 } 0484 ++iter; 0485 int endPos = (iter == appliedEnd) ? editLineEnd : (*iter)->trackingDestinationLineNumber(); 0486 for (int i = startPos; i < endPos; ++i) { 0487 sourceLines.append(oldLines.at(i - editLineNumber)); 0488 } 0489 } 0490 } 0491 0492 for (DifferenceListIterator iter = iterBegin; iter != iterEnd; ++iter) { 0493 removed << *iter; 0494 } 0495 insertPosition = m_differences.erase(iterBegin, iterEnd); 0496 0497 // Compute the Levenshtein table for two line sequences and construct the shortest possible edit script 0498 StringListPair* pair = new StringListPair(sourceLines, destinationLines); 0499 LevenshteinTable<StringListPair> table; 0500 table.createTable(pair); 0501 table.createListsOfMarkers(); 0502 MarkerList sourceMarkers = pair->markerListFirst(); 0503 MarkerList destinationMarkers = pair->markerListSecond(); 0504 0505 int currentSourceListLine = 0; 0506 int currentDestinationListLine = 0; 0507 MarkerListConstIterator sourceMarkerIter = sourceMarkers.constBegin(); 0508 MarkerListConstIterator destinationMarkerIter = destinationMarkers.constBegin(); 0509 const int terminatorLineNumber = sourceLines.size() + destinationLines.size() + 1; // A virtual offset for simpler computation - stands for infinity 0510 0511 // Process marker lists, converting pairs of Start-End markers into differences. 0512 // Marker in source list only stands for deletion, in source and destination lists - for change, in destination list only - for insertion. 0513 while (sourceMarkerIter != sourceMarkers.constEnd() || destinationMarkerIter != destinationMarkers.constEnd()) { 0514 int nextSourceListLine = sourceMarkerIter != sourceMarkers.constEnd() ? (*sourceMarkerIter)->offset() : terminatorLineNumber; 0515 int nextDestinationListLine = destinationMarkerIter != destinationMarkers.constEnd() ? (*destinationMarkerIter)->offset() : terminatorLineNumber; 0516 0517 // Advance to the nearest marker 0518 int linesToSkip = qMin(nextDestinationListLine - currentDestinationListLine, nextSourceListLine - currentSourceListLine); 0519 currentSourceListLine += linesToSkip; 0520 currentDestinationListLine += linesToSkip; 0521 Difference* diff = new Difference(sourceLineNumber + currentSourceListLine, destinationLineNumber + currentDestinationListLine); 0522 if (nextSourceListLine == currentSourceListLine) { 0523 processStartMarker(diff, sourceLines, sourceMarkerIter, currentSourceListLine, true); 0524 } 0525 if (nextDestinationListLine == currentDestinationListLine) { 0526 processStartMarker(diff, destinationLines, destinationMarkerIter, currentDestinationListLine, false); 0527 } 0528 computeDiffStats(diff); 0529 Q_ASSERT(diff->type() != Difference::Unchanged); 0530 diff->applyQuietly(true); 0531 diff->setTrackingDestinationLineNumber(diff->destinationLineNumber()); 0532 insertPosition = m_differences.insert(insertPosition, diff); 0533 ++insertPosition; 0534 inserted << diff; 0535 } 0536 // Update line numbers for differences that are after the edit 0537 for (; insertPosition != m_differences.end(); ++insertPosition) { 0538 (*insertPosition)->setTrackingDestinationLineNumber((*insertPosition)->trackingDestinationLineNumber() + (newLines.size() - oldLines.size())); 0539 } 0540 return qMakePair(inserted, removed); 0541 } 0542 0543 // Some common computing after diff contents have been filled. 0544 void DiffModel::computeDiffStats(Difference* diff) 0545 { 0546 if (diff->sourceLineCount() > 0 && diff->destinationLineCount() > 0) { 0547 diff->setType(Difference::Change); 0548 } else if (diff->sourceLineCount() > 0) { 0549 diff->setType(Difference::Delete); 0550 } else if (diff->destinationLineCount() > 0) { 0551 diff->setType(Difference::Insert); 0552 } 0553 diff->determineInlineDifferences(); 0554 } 0555 0556 // Helper method to extract duplicate code from DiffModel::linesChanged 0557 void DiffModel::processStartMarker(Difference* diff, const QStringList& lines, MarkerListConstIterator& currentMarker, int& currentListLine, bool isSource) 0558 { 0559 Q_ASSERT((*currentMarker)->type() == Marker::Start); 0560 ++currentMarker; 0561 Q_ASSERT((*currentMarker)->type() == Marker::End); 0562 int nextDestinationListLine = (*currentMarker)->offset(); 0563 for (; currentListLine < nextDestinationListLine; ++currentListLine) { 0564 if (isSource) { 0565 diff->addSourceLine(lines.at(currentListLine)); 0566 } else { 0567 diff->addDestinationLine(lines.at(currentListLine)); 0568 } 0569 } 0570 ++currentMarker; 0571 currentListLine = nextDestinationListLine; 0572 } 0573 0574 #include "moc_diffmodel.cpp" 0575 0576 /* vim: set ts=4 sw=4 noet: */