KompareDiff2

diffmodel.cpp
1 /*
2 SPDX-FileCopyrightText: 2001-2009 Otto Bruggeman <[email protected]>
3 SPDX-FileCopyrightText: 2001-2003 John Firebaugh <[email protected]>
4 
5 SPDX-License-Identifier: GPL-2.0-or-later
6 */
7 
8 #include "diffmodel.h"
9 
10 #include <komparediffdebug.h>
11 #include "difference.h"
12 #include "levenshteintable.h"
13 #include "stringlistpair.h"
14 #include "parserbase.h"
15 
16 using namespace Diff2;
17 
18 /** */
19 DiffModel::DiffModel(const QString& source, const QString& destination) :
20  m_source(source),
21  m_destination(destination),
22  m_sourcePath(),
23  m_destinationPath(),
24  m_sourceFile(),
25  m_destinationFile(),
26  m_sourceTimestamp(),
27  m_destinationTimestamp(),
28  m_sourceRevision(),
29  m_destinationRevision(),
30  m_appliedCount(0),
31  m_diffIndex(0),
32  m_selectedDifference(nullptr),
33  m_blended(false)
34 {
35  splitSourceInPathAndFileName();
36  splitDestinationInPathAndFileName();
37 }
38 
39 DiffModel::DiffModel() :
40  m_source(),
41  m_destination(),
42  m_sourcePath(),
43  m_destinationPath(),
44  m_sourceFile(),
45  m_destinationFile(),
46  m_sourceTimestamp(),
47  m_destinationTimestamp(),
48  m_sourceRevision(),
49  m_destinationRevision(),
50  m_appliedCount(0),
51  m_diffIndex(0),
52  m_selectedDifference(nullptr),
53  m_blended(false)
54 {
55 }
56 
57 /** */
58 DiffModel::~DiffModel()
59 {
60  m_selectedDifference = nullptr;
61 
62  qDeleteAll(m_hunks);
63  qDeleteAll(m_differences);
64 }
65 
66 void DiffModel::splitSourceInPathAndFileName()
67 {
68  int pos;
69 
70  if ((pos = m_source.lastIndexOf(QLatin1Char('/'))) >= 0)
71  m_sourcePath = m_source.mid(0, pos + 1);
72 
73  if ((pos = m_source.lastIndexOf(QLatin1Char('/'))) >= 0)
74  m_sourceFile = m_source.mid(pos + 1, m_source.length() - pos);
75  else
76  m_sourceFile = m_source;
77 
78  qCDebug(LIBKOMPAREDIFF2) << m_source << " was split into " << m_sourcePath << " and " << m_sourceFile;
79 }
80 
81 void DiffModel::splitDestinationInPathAndFileName()
82 {
83  int pos;
84 
85  if ((pos = m_destination.lastIndexOf(QLatin1Char('/'))) >= 0)
86  m_destinationPath = m_destination.mid(0, pos + 1);
87 
88  if ((pos = m_destination.lastIndexOf(QLatin1Char('/'))) >= 0)
89  m_destinationFile = m_destination.mid(pos + 1, m_destination.length() - pos);
90  else
91  m_destinationFile = m_destination;
92 
93  qCDebug(LIBKOMPAREDIFF2) << m_destination << " was split into " << m_destinationPath << " and " << m_destinationFile;
94 }
95 
96 DiffModel& DiffModel::operator=(const DiffModel& model)
97 {
98  if (&model != this) // Guard from self-assignment
99  {
100  m_source = model.m_source;
101  m_destination = model.m_destination;
102  m_sourcePath = model.m_sourcePath;
103  m_sourceFile = model.m_sourceFile;
104  m_sourceTimestamp = model.m_sourceTimestamp;
105  m_sourceRevision = model.m_sourceRevision;
106  m_destinationPath = model.m_destinationPath;
107  m_destinationFile = model.m_destinationFile;
108  m_destinationTimestamp = model.m_destinationTimestamp;
109  m_destinationRevision = model.m_destinationRevision;
110  m_appliedCount = model.m_appliedCount;
111 
112  m_diffIndex = model.m_diffIndex;
113  m_selectedDifference = model.m_selectedDifference;
114  }
115 
116  return *this;
117 }
118 
119 bool DiffModel::operator<(const DiffModel& model)
120 {
121  if (localeAwareCompareSource(model) < 0)
122  return true;
123  return false;
124 }
125 
126 int DiffModel::localeAwareCompareSource(const DiffModel& model)
127 {
128  qCDebug(LIBKOMPAREDIFF2) << "Path: " << model.m_sourcePath;
129  qCDebug(LIBKOMPAREDIFF2) << "File: " << model.m_sourceFile;
130 
131  int result = m_sourcePath.localeAwareCompare(model.m_sourcePath);
132 
133  if (result == 0)
134  return m_sourceFile.localeAwareCompare(model.m_sourceFile);
135 
136  return result;
137 }
138 
139 QString DiffModel::recreateDiff() const
140 {
141  // For now we'll always return a diff in the diff format
142  QString diff;
143 
144  // recreate header
145  const QChar tab = QLatin1Char('\t');
146  const QChar nl = QLatin1Char('\n');
147  diff += QStringLiteral("--- %1\t%2").arg(ParserBase::escapePath(m_source), m_sourceTimestamp);
148  if (!m_sourceRevision.isEmpty())
149  diff += tab + m_sourceRevision;
150  diff += nl;
151  diff += QStringLiteral("+++ %1\t%2").arg(ParserBase::escapePath(m_destination), m_destinationTimestamp);
152  if (!m_destinationRevision.isEmpty())
153  diff += tab + m_destinationRevision;
154  diff += nl;
155 
156  // recreate body by iterating over the hunks
157  DiffHunkListConstIterator hunkIt = m_hunks.begin();
158  DiffHunkListConstIterator hEnd = m_hunks.end();
159 
160  for (; hunkIt != hEnd; ++hunkIt)
161  {
162  if ((*hunkIt)->type() != DiffHunk::AddedByBlend)
163  diff += (*hunkIt)->recreateHunk();
164  }
165 
166  return diff;
167 }
168 
169 Difference* DiffModel::firstDifference()
170 {
171  qCDebug(LIBKOMPAREDIFF2) << "DiffModel::firstDifference()";
172  m_diffIndex = 0;
173  qCDebug(LIBKOMPAREDIFF2) << "m_diffIndex = " << m_diffIndex;
174 
175  m_selectedDifference = m_differences[ m_diffIndex ];
176 
177  return m_selectedDifference;
178 }
179 
180 Difference* DiffModel::lastDifference()
181 {
182  qCDebug(LIBKOMPAREDIFF2) << "DiffModel::lastDifference()";
183  m_diffIndex = m_differences.count() - 1;
184  qCDebug(LIBKOMPAREDIFF2) << "m_diffIndex = " << m_diffIndex;
185 
186  m_selectedDifference = m_differences[ m_diffIndex ];
187 
188  return m_selectedDifference;
189 }
190 
191 Difference* DiffModel::prevDifference()
192 {
193  qCDebug(LIBKOMPAREDIFF2) << "DiffModel::prevDifference()";
194  if (m_diffIndex > 0 && --m_diffIndex < m_differences.count())
195  {
196  qCDebug(LIBKOMPAREDIFF2) << "m_diffIndex = " << m_diffIndex;
197  m_selectedDifference = m_differences[ m_diffIndex ];
198  }
199  else
200  {
201  m_selectedDifference = nullptr;
202  m_diffIndex = 0;
203  qCDebug(LIBKOMPAREDIFF2) << "m_diffIndex = " << m_diffIndex;
204  }
205 
206  return m_selectedDifference;
207 }
208 
209 Difference* DiffModel::nextDifference()
210 {
211  qCDebug(LIBKOMPAREDIFF2) << "DiffModel::nextDifference()";
212  if (++m_diffIndex < m_differences.count())
213  {
214  qCDebug(LIBKOMPAREDIFF2) << "m_diffIndex = " << m_diffIndex;
215  m_selectedDifference = m_differences[ m_diffIndex ];
216  }
217  else
218  {
219  m_selectedDifference = nullptr;
220  m_diffIndex = 0; // just for safety...
221  qCDebug(LIBKOMPAREDIFF2) << "m_diffIndex = " << m_diffIndex;
222  }
223 
224  return m_selectedDifference;
225 }
226 
227 const QString DiffModel::sourceFile() const
228 {
229  return m_sourceFile;
230 }
231 
232 const QString DiffModel::destinationFile() const
233 {
234  return m_destinationFile;
235 }
236 
237 const QString DiffModel::sourcePath() const
238 {
239  return m_sourcePath;
240 }
241 
242 const QString DiffModel::destinationPath() const
243 {
244  return m_destinationPath;
245 }
246 
247 void DiffModel::setSourceFile(QString path)
248 {
249  m_source = path;
250  splitSourceInPathAndFileName();
251 }
252 
253 void DiffModel::setDestinationFile(QString path)
254 {
255  m_destination = path;
256  splitDestinationInPathAndFileName();
257 }
258 
259 void DiffModel::setSourceTimestamp(QString timestamp)
260 {
261  m_sourceTimestamp = timestamp;
262 }
263 
264 void DiffModel::setDestinationTimestamp(QString timestamp)
265 {
266  m_destinationTimestamp = timestamp;
267 }
268 
269 void DiffModel::setSourceRevision(QString revision)
270 {
271  m_sourceRevision = revision;
272 }
273 
274 void DiffModel::setDestinationRevision(QString revision)
275 {
276  m_destinationRevision = revision;
277 }
278 
279 void DiffModel::addHunk(DiffHunk* hunk)
280 {
281  m_hunks.append(hunk);
282 }
283 
284 void DiffModel::addDiff(Difference* diff)
285 {
286  m_differences.append(diff);
287  connect(diff, &Difference::differenceApplied,
288  this, &DiffModel::slotDifferenceApplied);
289 }
290 
291 bool DiffModel::hasUnsavedChanges(void) const
292 {
293  DifferenceListConstIterator diffIt = m_differences.begin();
294  DifferenceListConstIterator endIt = m_differences.end();
295 
296  for (; diffIt != endIt; ++diffIt)
297  {
298  if ((*diffIt)->isUnsaved())
299  return true;
300  }
301 
302  return false;
303 }
304 
305 void DiffModel::applyDifference(bool apply)
306 {
307  bool appliedState = m_selectedDifference->applied();
308  if (appliedState == apply)
309  {
310  return;
311  }
312  if (apply && !m_selectedDifference->applied())
313  ++m_appliedCount;
314  else if (!apply && m_selectedDifference->applied())
315  --m_appliedCount;
316 
317  m_selectedDifference->apply(apply);
318 }
319 
320 static int GetDifferenceDelta(Difference* diff)
321 {
322  int delta = diff->destinationLineCount() - diff->sourceLineCount();
323  if (!diff->applied())
324  {
325  delta = -delta;
326  }
327  return delta;
328 }
329 
330 void DiffModel::slotDifferenceApplied(Difference* diff)
331 {
332  int delta = GetDifferenceDelta(diff);
333  for (Difference* current : qAsConst(m_differences)) {
334  if (current->destinationLineNumber() > diff->destinationLineNumber())
335  {
336  current->setTrackingDestinationLineNumber(current->trackingDestinationLineNumber() + delta);
337  }
338  }
339 }
340 
341 void DiffModel::applyAllDifferences(bool apply)
342 {
343  if (apply)
344  {
345  m_appliedCount = m_differences.count();
346  }
347  else
348  {
349  m_appliedCount = 0;
350  }
351 
352  DifferenceListIterator diffIt = m_differences.begin();
353  DifferenceListIterator dEnd = m_differences.end();
354 
355  int totalDelta = 0;
356  for (; diffIt != dEnd; ++diffIt)
357  {
358  (*diffIt)->setTrackingDestinationLineNumber((*diffIt)->trackingDestinationLineNumber() + totalDelta);
359  bool appliedState = (*diffIt)->applied();
360  if (appliedState == apply)
361  {
362  continue;
363  }
364  (*diffIt)->applyQuietly(apply);
365  int currentDelta = GetDifferenceDelta(*diffIt);
366  totalDelta += currentDelta;
367  }
368 }
369 
370 bool DiffModel::setSelectedDifference(Difference* diff)
371 {
372  qCDebug(LIBKOMPAREDIFF2) << "diff = " << diff;
373  qCDebug(LIBKOMPAREDIFF2) << "m_selectedDifference = " << m_selectedDifference;
374 
375  if (diff != m_selectedDifference)
376  {
377  if ((m_differences.indexOf(diff)) == -1)
378  return false;
379  // Do not set m_diffIndex if it cant be found
380  m_diffIndex = m_differences.indexOf(diff);
381  qCDebug(LIBKOMPAREDIFF2) << "m_diffIndex = " << m_diffIndex;
382  m_selectedDifference = diff;
383  }
384 
385  return true;
386 }
387 
388 QPair<QList<Difference*>, QList<Difference*> > DiffModel::linesChanged(const QStringList& oldLines, const QStringList& newLines, int editLineNumber)
389 {
390  // These two will be returned as the function result
391  QList<Difference*> inserted;
392  QList<Difference*> removed;
393  if (oldLines.size() == 0 && newLines.size() == 0) {
394  return qMakePair(QList<Difference*>(), QList<Difference*>());
395  }
396  int editLineEnd = editLineNumber + oldLines.size();
397  // Find the range of differences [iterBegin, iterEnd) that should be updated
398  // TODO: assume that differences are ordered by starting line. Check that this is always the case
399  DifferenceList applied;
400  DifferenceListIterator iterBegin; // first diff ending a line before editLineNo or later
401  for (iterBegin = m_differences.begin(); iterBegin != m_differences.end(); ++iterBegin) {
402  // If the difference ends a line before the edit starts, they should be merged if this difference is applied.
403  // Also it should be merged if it starts on editLineNumber, otherwise there will be two markers for the same line
404  int lineAfterLast = (*iterBegin)->trackingDestinationLineEnd();
405  if (lineAfterLast > editLineNumber || (lineAfterLast == editLineNumber &&
406  ((*iterBegin)->applied() || (*iterBegin)->trackingDestinationLineNumber() == editLineNumber))) {
407  break;
408  }
409  }
410  DifferenceListIterator iterEnd;
411  for (iterEnd = iterBegin; iterEnd != m_differences.end(); ++iterEnd) {
412  // If the difference starts a line after the edit ends, it should still be merged if it is applied
413  int firstLine = (*iterEnd)->trackingDestinationLineNumber();
414  if (firstLine > editLineEnd || (!(*iterEnd)->applied() && firstLine == editLineEnd)) {
415  break;
416  }
417  if ((*iterEnd)->applied()) {
418  applied.append(*iterEnd);
419  }
420  }
421 
422  // Compute line numbers in source and destination to which the for diff line sequences (will be created later)
423  int sourceLineNumber;
424  int destinationLineNumber;
425  if (iterBegin == m_differences.end()) { // All existing diffs are after the change
426  destinationLineNumber = editLineNumber;
427  if (!m_differences.isEmpty()) {
428  sourceLineNumber = m_differences.last()->sourceLineEnd() - (m_differences.last()->trackingDestinationLineEnd() - editLineNumber);
429  } else {
430  sourceLineNumber = destinationLineNumber;
431  }
432  } else if (!(*iterBegin)->applied() || (*iterBegin)->trackingDestinationLineNumber() >= editLineNumber) {
433  destinationLineNumber = editLineNumber;
434  sourceLineNumber = (*iterBegin)->sourceLineNumber() - ((*iterBegin)->trackingDestinationLineNumber() - editLineNumber);
435  } else {
436  sourceLineNumber = (*iterBegin)->sourceLineNumber();
437  destinationLineNumber = (*iterBegin)->trackingDestinationLineNumber();
438  }
439 
440  // Only the applied differences are of interest, unapplied can be safely removed
441  DifferenceListConstIterator appliedBegin = applied.constBegin();
442  DifferenceListConstIterator appliedEnd = applied.constEnd();
443 
444  // Now create a sequence of lines for the destination file and the corresponding lines in source
445  QStringList sourceLines;
446  QStringList destinationLines;
447  DifferenceListIterator insertPosition; // where to insert the created diffs
448  if (appliedBegin == appliedEnd) {
449  destinationLines = newLines;
450  sourceLines = oldLines;
451  } else {
452  // Create the destination line sequence
453  int firstDestinationLineNumber = (*appliedBegin)->trackingDestinationLineNumber();
454  for (int lineNumber = firstDestinationLineNumber; lineNumber < editLineNumber; ++lineNumber) {
455  destinationLines.append((*appliedBegin)->destinationLineAt(lineNumber - firstDestinationLineNumber)->string());
456  }
457  for (const QString& line : newLines) {
458  destinationLines.append(line);
459  }
460  DifferenceListConstIterator appliedLast = appliedEnd;
461  --appliedLast;
462  int lastDestinationLineNumber = (*appliedLast)->trackingDestinationLineNumber();
463  for (int lineNumber = editLineEnd; lineNumber < (*appliedLast)->trackingDestinationLineEnd(); ++lineNumber) {
464  destinationLines.append((*appliedLast)->destinationLineAt(lineNumber - lastDestinationLineNumber)->string());
465  }
466 
467  // Create the source line sequence
468  if ((*appliedBegin)->trackingDestinationLineNumber() >= editLineNumber) {
469  for (int i = editLineNumber; i < (*appliedBegin)->trackingDestinationLineNumber(); ++i) {
470  sourceLines.append(oldLines.at(i - editLineNumber));
471  }
472  }
473 
474  for (DifferenceListConstIterator iter = appliedBegin; iter != appliedEnd;) {
475  int startPos = (*iter)->trackingDestinationLineNumber();
476  if ((*iter)->applied()) {
477  for (int i = 0; i < (*iter)->sourceLineCount(); ++i) {
478  sourceLines.append((*iter)->sourceLineAt(i)->string());
479  }
480  startPos = (*iter)->trackingDestinationLineEnd();
481  } else if (startPos < editLineNumber) {
482  startPos = editLineNumber;
483  }
484  ++iter;
485  int endPos = (iter == appliedEnd) ? editLineEnd : (*iter)->trackingDestinationLineNumber();
486  for (int i = startPos; i < endPos; ++i) {
487  sourceLines.append(oldLines.at(i - editLineNumber));
488  }
489  }
490  }
491 
492  for (DifferenceListIterator iter = iterBegin; iter != iterEnd; ++iter) {
493  removed << *iter;
494  }
495  insertPosition = m_differences.erase(iterBegin, iterEnd);
496 
497  // Compute the Levenshtein table for two line sequences and construct the shortest possible edit script
498  StringListPair* pair = new StringListPair(sourceLines, destinationLines);
500  table.createTable(pair);
501  table.createListsOfMarkers();
502  MarkerList sourceMarkers = pair->markerListFirst();
503  MarkerList destinationMarkers = pair->markerListSecond();
504 
505  int currentSourceListLine = 0;
506  int currentDestinationListLine = 0;
507  MarkerListConstIterator sourceMarkerIter = sourceMarkers.constBegin();
508  MarkerListConstIterator destinationMarkerIter = destinationMarkers.constBegin();
509  const int terminatorLineNumber = sourceLines.size() + destinationLines.size() + 1; // A virtual offset for simpler computation - stands for infinity
510 
511  // Process marker lists, converting pairs of Start-End markers into differences.
512  // Marker in source list only stands for deletion, in source and destination lists - for change, in destination list only - for insertion.
513  while (sourceMarkerIter != sourceMarkers.constEnd() || destinationMarkerIter != destinationMarkers.constEnd()) {
514  int nextSourceListLine = sourceMarkerIter != sourceMarkers.constEnd() ? (*sourceMarkerIter)->offset() : terminatorLineNumber;
515  int nextDestinationListLine = destinationMarkerIter != destinationMarkers.constEnd() ? (*destinationMarkerIter)->offset() : terminatorLineNumber;
516 
517  // Advance to the nearest marker
518  int linesToSkip = qMin(nextDestinationListLine - currentDestinationListLine, nextSourceListLine - currentSourceListLine);
519  currentSourceListLine += linesToSkip;
520  currentDestinationListLine += linesToSkip;
521  Difference* diff = new Difference(sourceLineNumber + currentSourceListLine, destinationLineNumber + currentDestinationListLine);
522  if (nextSourceListLine == currentSourceListLine) {
523  processStartMarker(diff, sourceLines, sourceMarkerIter, currentSourceListLine, true);
524  }
525  if (nextDestinationListLine == currentDestinationListLine) {
526  processStartMarker(diff, destinationLines, destinationMarkerIter, currentDestinationListLine, false);
527  }
528  computeDiffStats(diff);
529  Q_ASSERT(diff->type() != Difference::Unchanged);
530  diff->applyQuietly(true);
531  diff->setTrackingDestinationLineNumber(diff->destinationLineNumber());
532  insertPosition = m_differences.insert(insertPosition, diff);
533  ++insertPosition;
534  inserted << diff;
535  }
536  // Update line numbers for differences that are after the edit
537  for (; insertPosition != m_differences.end(); ++insertPosition) {
538  (*insertPosition)->setTrackingDestinationLineNumber((*insertPosition)->trackingDestinationLineNumber() + (newLines.size() - oldLines.size()));
539  }
540  return qMakePair(inserted, removed);
541 }
542 
543 // Some common computing after diff contents have been filled.
544 void DiffModel::computeDiffStats(Difference* diff)
545 {
546  if (diff->sourceLineCount() > 0 && diff->destinationLineCount() > 0) {
547  diff->setType(Difference::Change);
548  } else if (diff->sourceLineCount() > 0) {
549  diff->setType(Difference::Delete);
550  } else if (diff->destinationLineCount() > 0) {
551  diff->setType(Difference::Insert);
552  }
554 }
555 
556 // Helper method to extract duplicate code from DiffModel::linesChanged
557 void DiffModel::processStartMarker(Difference* diff, const QStringList& lines, MarkerListConstIterator& currentMarker, int& currentListLine, bool isSource)
558 {
559  Q_ASSERT((*currentMarker)->type() == Marker::Start);
560  ++currentMarker;
561  Q_ASSERT((*currentMarker)->type() == Marker::End);
562  int nextDestinationListLine = (*currentMarker)->offset();
563  for (; currentListLine < nextDestinationListLine; ++currentListLine) {
564  if (isSource) {
565  diff->addSourceLine(lines.at(currentListLine));
566  } else {
567  diff->addDestinationLine(lines.at(currentListLine));
568  }
569  }
570  ++currentMarker;
571  currentListLine = nextDestinationListLine;
572 }
573 
574 /* vim: set ts=4 sw=4 noet: */
void append(const T &value)
A model describing the differences between two files.
Definition: diffmodel.h:23
Diff2 namespace.
Definition: cvsdiffparser.h:12
void determineInlineDifferences()
This method will calculate the differences between the individual strings and store them as Markers.
Definition: difference.cpp:86
int count(const T &value) const const
QPair< QList< Difference * >, QList< Difference * > > linesChanged(const QStringList &oldLines, const QStringList &newLines, int editLineNumber)
oldlines - lines that were removed.
Definition: diffmodel.cpp:388
QList::const_iterator constBegin() const const
int lastIndexOf(QChar ch, int from, Qt::CaseSensitivity cs) const const
QMetaObject::Connection connect(const QObject *sender, const char *signal, const QObject *receiver, const char *method, Qt::ConnectionType type)
void applyQuietly(bool apply)
Apply without emitting any signals.
Definition: difference.cpp:77
int size() const const
int indexOf(const T &value, int from) const const
bool isEmpty() const const
int length() const const
const T & at(int i) const const
bool isEmpty() const const
void insert(int i, const T &value)
T & last()
int localeAwareCompare(const QString &other) const const
QList::const_iterator constEnd() const const
QList::iterator erase(QList::iterator pos)
QString arg(qlonglong a, int fieldWidth, int base, QChar fillChar) const const
unsigned int createTable(SequencePair *sequences)
This calculates the levenshtein distance of 2 sequences.
QList::iterator begin()
DiffHunk.
Definition: diffhunk.h:22
A difference.
Definition: difference.h:119
QList::iterator end()
Computes the Levenshtein distance between two sequences.
QString mid(int position, int n) const const
This file is part of the KDE documentation.
Documentation copyright © 1996-2022 The KDE developers.
Generated on Wed Sep 28 2022 03:51:41 by doxygen 1.8.17 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.