From ce5a3b3c9b0d1c3ad082716d4644bbd5544558d1 Mon Sep 17 00:00:00 2001 From: sdottaka Date: Sun, 5 May 2013 15:22:59 +0900 Subject: [PATCH] Separte diff3 algorithm from DiffWrapper.cpp and stringdiffs.cpp into Diff3.h --- Src/Diff3.h | 257 ++++++++++++++++++++++++++++++++++++++++++++++ Src/DiffList.cpp | 44 ++++---- Src/DiffList.h | 13 ++- Src/DiffWrapper.cpp | 234 +---------------------------------------- Src/DiffWrapper.h | 1 - Src/Merge.vcxproj | 1 + Src/Merge.vcxproj.filters | 3 + Src/stringdiffs.cpp | 203 ++---------------------------------- Src/stringdiffs.h | 2 + 9 files changed, 303 insertions(+), 455 deletions(-) create mode 100644 Src/Diff3.h diff --git a/Src/Diff3.h b/Src/Diff3.h new file mode 100644 index 000000000..22c2de9f1 --- /dev/null +++ b/Src/Diff3.h @@ -0,0 +1,257 @@ +#ifndef __DIFF3_H__ +#define __DIFF3_H__ + +#include +#ifdef _DEBUG +# include +# include +#endif +#include "DiffList.h" + +/* diff3 algorithm. It is almost the same as GNU diff3's algorithm */ +template +size_t Make3wayDiff(std::vector& diff3, const std::vector& diff10, const std::vector& diff12, const std::vector& diff02, bool ignore_regexp_list) +{ + size_t diff10count = diff10.size(); + size_t diff12count = diff12.size(); + size_t diff02count = diff02.size(); + + size_t diff10i = 0; + size_t diff12i = 0; + size_t diff02i = 0; + size_t diff3i = 0; + + size_t diff10itmp; + size_t diff12itmp; + size_t diff02itmp = 0; + + bool lastDiffBlockIsDiff12; + bool firstDiffBlockIsDiff12; + + Element dr3, dr10, dr12, dr02, dr10first, dr10last, dr12first, dr12last; + + int linelast0 = 0; + int linelast1 = 0; + int linelast2 = 0; + + for (;;) + { + if (diff10i >= diff10count && diff12i >= diff12count) + break; + + /* + * merge overlapped diff blocks + * diff10 is diff blocks between file1 and file0. + * diff12 is diff blocks between file1 and file2. + * + * diff12 + * diff10 diff3 + * |~~~| |~~~| + * firstDiffBlock | | | | + * | | |~~~| | | + * |___| | | | | + * | | -> | | + * |~~~| |___| | | + * lastDiffBlock | | | | + * |___| |___| + */ + + if (diff10i >= diff10count && diff12i < diff12count) + { + dr12first = diff12.at(diff12i); + dr12last = dr12first; + firstDiffBlockIsDiff12 = true; + } + else if (diff10i < diff10count && diff12i >= diff12count) + { + dr10first = diff10.at(diff10i); + dr10last = dr10first; + firstDiffBlockIsDiff12 = false; + } + else + { + dr10first = diff10.at(diff10i); + dr12first = diff12.at(diff12i); + dr10last = dr10first; + dr12last = dr12first; + if (dr12first.begin[0] <= dr10first.begin[0]) + firstDiffBlockIsDiff12 = true; + else + firstDiffBlockIsDiff12 = false; + } + lastDiffBlockIsDiff12 = firstDiffBlockIsDiff12; + + diff10itmp = diff10i; + diff12itmp = diff12i; + for (;;) + { + if (diff10itmp >= diff10count || diff12itmp >= diff12count) + break; + + dr10 = diff10.at(diff10itmp); + dr12 = diff12.at(diff12itmp); + + if (dr10.end[0] == dr12.end[0]) + { + diff10itmp++; + lastDiffBlockIsDiff12 = true; + + dr10last = dr10; + dr12last = dr12; + break; + } + + if (lastDiffBlockIsDiff12) + { + if (dr12.end[0] + 1 < dr10.begin[0]) + break; + } + else + { + if (dr10.end[0] + 1 < dr12.begin[0]) + break; + } + + if (dr12.end[0] > dr10.end[0]) + { + diff10itmp++; + lastDiffBlockIsDiff12 = true; + } + else + { + diff12itmp++; + lastDiffBlockIsDiff12 = false; + } + + dr10last = dr10; + dr12last = dr12; + } + + if (lastDiffBlockIsDiff12) + diff12itmp++; + else + diff10itmp++; + + if (firstDiffBlockIsDiff12) + { + dr3.begin[1] = dr12first.begin[0]; + dr3.begin[2] = dr12first.begin[1]; + if (diff10itmp == diff10i) + dr3.begin[0] = dr3.begin[1] - linelast1 + linelast0; + else + dr3.begin[0] = dr3.begin[1] - dr10first.begin[0] + dr10first.begin[1]; + } + else + { + dr3.begin[0] = dr10first.begin[1]; + dr3.begin[1] = dr10first.begin[0]; + if (diff12itmp == diff12i) + dr3.begin[2] = dr3.begin[1] - linelast1 + linelast2; + else + dr3.begin[2] = dr3.begin[1] - dr12first.begin[0] + dr12first.begin[1]; + } + + if (lastDiffBlockIsDiff12) + { + dr3.end[1] = dr12last.end[0]; + dr3.end[2] = dr12last.end[1]; + if (diff10itmp == diff10i) + dr3.end[0] = dr3.end[1] - linelast1 + linelast0; + else + dr3.end[0] = dr3.end[1] - dr10last.end[0] + dr10last.end[1]; + } + else + { + dr3.end[0] = dr10last.end[1]; + dr3.end[1] = dr10last.end[0]; + if (diff12itmp == diff12i) + dr3.end[2] = dr3.end[1] - linelast1 + linelast2; + else + dr3.end[2] = dr3.end[1] - dr12last.end[0] + dr12last.end[1]; + } + + linelast0 = dr3.end[0] + 1; + linelast1 = dr3.end[1] + 1; + linelast2 = dr3.end[2] + 1; + + if (diff10i == diff10itmp) + dr3.op = OP_3RDONLY; + else if (diff12i == diff12itmp) + dr3.op = OP_1STONLY; + else + { + dr3.op = OP_2NDONLY; + for (diff02itmp = diff02i; diff02itmp < diff02count; diff02itmp++) + { + dr02 = diff02.at(diff02itmp); + if (dr02.end[1] < dr3.begin[2]) + continue; + + if (dr02.begin[1] <= dr3.end[2]) + dr3.op = OP_DIFF; + break; + } + } + + if (ignore_regexp_list) + { + bool bTrivialDiff10 = true; + bool bTrivialDiff12 = true; + size_t i; + + for (i = diff10i; i < diff10itmp; i++) + { + dr10 = diff10.at(i); + if (dr10.op != OP_TRIVIAL) + { + bTrivialDiff10 = false; + break; + } + } + + for (i = diff12i; i < diff12itmp; i++) + { + dr12 = diff12.at(i); + if (dr12.op != OP_TRIVIAL) + { + bTrivialDiff12 = false; + break; + } + } + + if (bTrivialDiff10 && bTrivialDiff12) + dr3.op = OP_TRIVIAL; + } + + diff3.push_back(dr3); + +#ifdef _DEBUG + Poco::Debugger::message(Poco::format("left=%d,%d middle=%d,%d right=%d,%d", + dr3.begin[0], dr3.end[0], dr3.begin[1], dr3.end[1], dr3.begin[2], dr3.end[2])); + Poco::Debugger::message(Poco::format("op=%d\n", (int)dr3.op)); +#endif + + diff3i++; + diff10i = diff10itmp; + diff12i = diff12itmp; + diff02i = diff02itmp; + } + + for (size_t i = 0; i < diff3i; i++) + { + Element& dr3 = diff3.at(i); + if (i < diff3i - 1) + { + Element& dr3next = diff3.at(i + 1); + for (int j = 0; j < 3; j++) + { + if (dr3.end[j] >= dr3next.begin[j]) + dr3.end[j] = dr3next.begin[j] - 1; + } + } + } + + return diff3i; +} + +#endif diff --git a/Src/DiffList.cpp b/Src/DiffList.cpp index d19cb3be2..ccbc827e8 100644 --- a/Src/DiffList.cpp +++ b/Src/DiffList.cpp @@ -210,7 +210,7 @@ const DIFFRANGE * DiffList::DiffRangeAt(int nDiff) const { if (nDiff >= 0 && nDiff < (int) m_diffs.size()) { - return &m_diffs[nDiff].diffrange; + return &m_diffs[nDiff]; } else { @@ -229,7 +229,7 @@ bool DiffList::SetDiff(int nDiff, const DIFFRANGE & di) { if (nDiff < (int) m_diffs.size()) { - m_diffs[nDiff].diffrange = di; + m_diffs[nDiff] = di; return true; } else @@ -453,7 +453,7 @@ void DiffList::ConstructSignificantChain() // must be called after diff list is entirely populated for (int i = 0; i < size; ++i) { - if (m_diffs[i].diffrange.op == OP_TRIVIAL) + if (m_diffs[i].op == OP_TRIVIAL) { m_diffs[i].prev = -1; m_diffs[i].next = -1; @@ -467,37 +467,37 @@ void DiffList::ConstructSignificantChain() if (m_firstSignificant == -1) m_firstSignificant = i; m_lastSignificant = i; - if (m_diffs[i].diffrange.op != OP_TRIVIAL && m_diffs[i].diffrange.op != OP_3RDONLY) + if (m_diffs[i].op != OP_TRIVIAL && m_diffs[i].op != OP_3RDONLY) { if (m_firstSignificantLeftMiddle == -1) m_firstSignificantLeftMiddle = i; m_lastSignificantLeftMiddle = i; } - if (m_diffs[i].diffrange.op != OP_TRIVIAL && m_diffs[i].diffrange.op != OP_2NDONLY) + if (m_diffs[i].op != OP_TRIVIAL && m_diffs[i].op != OP_2NDONLY) { if (m_firstSignificantLeftRight == -1) m_firstSignificantLeftRight = i; m_lastSignificantLeftRight = i; } - if (m_diffs[i].diffrange.op != OP_TRIVIAL && m_diffs[i].diffrange.op != OP_1STONLY) + if (m_diffs[i].op != OP_TRIVIAL && m_diffs[i].op != OP_1STONLY) { if (m_firstSignificantMiddleRight == -1) m_firstSignificantMiddleRight = i; m_lastSignificantMiddleRight = i; } - if (m_diffs[i].diffrange.op == OP_1STONLY) + if (m_diffs[i].op == OP_1STONLY) { if (m_firstSignificantLeftOnly == -1) m_firstSignificantLeftOnly = i; m_lastSignificantLeftOnly = i; } - if (m_diffs[i].diffrange.op == OP_2NDONLY) + if (m_diffs[i].op == OP_2NDONLY) { if (m_firstSignificantMiddleOnly == -1) m_firstSignificantMiddleOnly = i; m_lastSignificantMiddleOnly = i; } - if (m_diffs[i].diffrange.op == OP_3RDONLY) + if (m_diffs[i].op == OP_3RDONLY) { if (m_firstSignificantRightOnly == -1) m_firstSignificantRightOnly = i; @@ -689,27 +689,27 @@ int DiffList::NextSignificant3wayDiff(int nDiff, int nDiffType) const switch (nDiffType) { case THREEWAYDIFFTYPE_LEFTMIDDLE: - if (m_diffs[nDiff].diffrange.op != OP_3RDONLY) + if (m_diffs[nDiff].op != OP_3RDONLY) return nDiff; break; case THREEWAYDIFFTYPE_LEFTRIGHT: - if (m_diffs[nDiff].diffrange.op != OP_2NDONLY) + if (m_diffs[nDiff].op != OP_2NDONLY) return nDiff; break; case THREEWAYDIFFTYPE_MIDDLERIGHT: - if (m_diffs[nDiff].diffrange.op != OP_1STONLY) + if (m_diffs[nDiff].op != OP_1STONLY) return nDiff; break; case THREEWAYDIFFTYPE_LEFTONLY: - if (m_diffs[nDiff].diffrange.op == OP_1STONLY) + if (m_diffs[nDiff].op == OP_1STONLY) return nDiff; break; case THREEWAYDIFFTYPE_MIDDLEONLY: - if (m_diffs[nDiff].diffrange.op == OP_2NDONLY) + if (m_diffs[nDiff].op == OP_2NDONLY) return nDiff; break; case THREEWAYDIFFTYPE_RIGHTONLY: - if (m_diffs[nDiff].diffrange.op == OP_3RDONLY) + if (m_diffs[nDiff].op == OP_3RDONLY) return nDiff; break; } @@ -730,27 +730,27 @@ int DiffList::PrevSignificant3wayDiff(int nDiff, int nDiffType) const switch (nDiffType) { case THREEWAYDIFFTYPE_LEFTMIDDLE: - if (m_diffs[nDiff].diffrange.op != OP_3RDONLY) + if (m_diffs[nDiff].op != OP_3RDONLY) return nDiff; break; case THREEWAYDIFFTYPE_LEFTRIGHT: - if (m_diffs[nDiff].diffrange.op != OP_2NDONLY) + if (m_diffs[nDiff].op != OP_2NDONLY) return nDiff; break; case THREEWAYDIFFTYPE_MIDDLERIGHT: - if (m_diffs[nDiff].diffrange.op != OP_1STONLY) + if (m_diffs[nDiff].op != OP_1STONLY) return nDiff; break; case THREEWAYDIFFTYPE_LEFTONLY: - if (m_diffs[nDiff].diffrange.op == OP_1STONLY) + if (m_diffs[nDiff].op == OP_1STONLY) return nDiff; break; case THREEWAYDIFFTYPE_MIDDLEONLY: - if (m_diffs[nDiff].diffrange.op == OP_2NDONLY) + if (m_diffs[nDiff].op == OP_2NDONLY) return nDiff; break; case THREEWAYDIFFTYPE_RIGHTONLY: - if (m_diffs[nDiff].diffrange.op == OP_3RDONLY) + if (m_diffs[nDiff].op == OP_3RDONLY) return nDiff; break; } @@ -851,7 +851,7 @@ void DiffList::Swap(int index1, int index2) vector::const_iterator iterEnd = m_diffs.end(); while (iter != iterEnd) { - (*iter).diffrange.swap_sides(index1, index2); + (*iter).swap_sides(index1, index2); ++iter; } } diff --git a/Src/DiffList.h b/Src/DiffList.h index 656d1b479..fc319f664 100644 --- a/Src/DiffList.h +++ b/Src/DiffList.h @@ -72,7 +72,11 @@ struct DIFFRANGE int dend[3]; /**< Synchronised (ghost lines added) last diff line in file1,2,3 */ int blank[3]; /**< Number of blank lines in file1,2,3 */ OP_TYPE op; /**< Operation done with this diff */ - DIFFRANGE() { memset(this, 0, sizeof(*this)); } + DIFFRANGE() + { + memset(this, 0, sizeof(*this)); + blank[0] = blank[1] = blank[2] = -1; + } void swap_sides(int index1, int index2); }; @@ -103,14 +107,13 @@ public: * * Next and prev are array indices used by the owner (DiffList) */ -struct DiffRangeInfo +struct DiffRangeInfo: public DIFFRANGE { - DIFFRANGE diffrange; size_t next; /**< link (array index) for doubly-linked chain of non-trivial DIFFRANGEs */ size_t prev; /**< link (array index) for doubly-linked chain of non-trivial DIFFRANGEs */ DiffRangeInfo() { InitLinks(); } - DiffRangeInfo(const DIFFRANGE & di) : diffrange(di) { InitLinks(); } + DiffRangeInfo(const DIFFRANGE & di) : DIFFRANGE(di) { InitLinks(); } void InitLinks() { next = prev = -1; } }; @@ -168,6 +171,8 @@ public: void Swap(int index1, int index2); void GetExtraLinesCounts(int nFiles, int extras[]); + std::vector& GetDiffRangeInfoVector() { return m_diffs; } + private: std::vector m_diffs; /**< Difference list. */ int m_firstSignificant; /**< Index of first significant diff in m_diffs */ diff --git a/Src/DiffWrapper.cpp b/Src/DiffWrapper.cpp index 2845e824c..e90309624 100644 --- a/Src/DiffWrapper.cpp +++ b/Src/DiffWrapper.cpp @@ -43,6 +43,7 @@ #include "MovedLines.h" #include "FilterList.h" #include "diff.h" +#include "Diff3.h" #include "FileTransform.h" #include "LogFile.h" #include "paths.h" @@ -1448,7 +1449,7 @@ CDiffWrapper::LoadWinMergeDiffsFromDiffUtilsScript3( } } - Make3wayDiff(*m_pDiffList, diff10, diff12, diff02); + Make3wayDiff(m_pDiffList->GetDiffRangeInfoVector(), diff10.GetDiffRangeInfoVector(), diff12.GetDiffRangeInfoVector(), diff02.GetDiffRangeInfoVector(), ignore_regexp_list ? true : false); } void CDiffWrapper::WritePatchFileHeader(enum output_style output_style, bool bAppendFiles) @@ -1684,234 +1685,3 @@ void CopyDiffutilTextStats(file_data *inf, DiffFileData * diffData) CopyTextStats(&inf[0], &diffData->m_textStats[0]); CopyTextStats(&inf[1], &diffData->m_textStats[1]); } - -/* diff3 algorithm. It is almost the same as GNU diff3's algorithm */ -int CDiffWrapper::Make3wayDiff(DiffList& diff3, DiffList& diff10, DiffList& diff12, DiffList& diff02) -{ - int diff10count = diff10.GetSize(); - int diff12count = diff12.GetSize(); - int diff02count = diff02.GetSize(); - - int diff10i = 0; - int diff12i = 0; - int diff02i = 0; - int diff3i = 0; - - int diff10itmp; - int diff12itmp; - int diff02itmp = 0; - - bool lastDiffBlockIsDiff12; - bool firstDiffBlockIsDiff12; - - DIFFRANGE dr3, dr10, dr12, dr02, dr10first, dr10last, dr12first, dr12last; - dr3.blank[0] = dr3.blank[1] = dr3.blank[2] = -1; - - int linelast0 = 0; - int linelast1 = 0; - int linelast2 = 0; - - for (;;) - { - if (diff10i >= diff10count && diff12i >= diff12count) - break; - - /* - * merge overlapped diff blocks - * diff10 is diff blocks between file1 and file0. - * diff12 is diff blocks between file1 and file2. - * - * diff12 - * diff10 diff3 - * |~~~| |~~~| - * firstDiffBlock | | | | - * | | |~~~| | | - * |___| | | | | - * | | -> | | - * |~~~| |___| | | - * lastDiffBlock | | | | - * |___| |___| - */ - - if (diff10i >= diff10count && diff12i < diff12count) - { - diff12.GetDiff(diff12i, dr12first); - dr12last = dr12first; - firstDiffBlockIsDiff12 = true; - } - else if (diff10i < diff10count && diff12i >= diff12count) - { - diff10.GetDiff(diff10i, dr10first); - dr10last = dr10first; - firstDiffBlockIsDiff12 = false; - } - else - { - diff10.GetDiff(diff10i, dr10first); - diff12.GetDiff(diff12i, dr12first); - dr10last = dr10first; - dr12last = dr12first; - if (dr12first.begin[0] <= dr10first.begin[0]) - firstDiffBlockIsDiff12 = true; - else - firstDiffBlockIsDiff12 = false; - } - lastDiffBlockIsDiff12 = firstDiffBlockIsDiff12; - - diff10itmp = diff10i; - diff12itmp = diff12i; - for (;;) - { - if (diff10itmp >= diff10count || diff12itmp >= diff12count) - break; - - diff10.GetDiff(diff10itmp, dr10); - diff12.GetDiff(diff12itmp, dr12); - - if (dr10.end[0] == dr12.end[0]) - { - diff10itmp++; - lastDiffBlockIsDiff12 = true; - - dr10last = dr10; - dr12last = dr12; - break; - } - - if (lastDiffBlockIsDiff12) - { - if (dr12.end[0] + 1 < dr10.begin[0]) - break; - } - else - { - if (dr10.end[0] + 1 < dr12.begin[0]) - break; - } - - if (dr12.end[0] > dr10.end[0]) - { - diff10itmp++; - lastDiffBlockIsDiff12 = true; - } - else - { - diff12itmp++; - lastDiffBlockIsDiff12 = false; - } - - dr10last = dr10; - dr12last = dr12; - } - - if (lastDiffBlockIsDiff12) - diff12itmp++; - else - diff10itmp++; - - if (firstDiffBlockIsDiff12) - { - dr3.begin[1] = dr12first.begin[0]; - dr3.begin[2] = dr12first.begin[1]; - if (diff10itmp == diff10i) - dr3.begin[0] = dr3.begin[1] - linelast1 + linelast0; - else - dr3.begin[0] = dr3.begin[1] - dr10first.begin[0] + dr10first.begin[1]; - } - else - { - dr3.begin[0] = dr10first.begin[1]; - dr3.begin[1] = dr10first.begin[0]; - if (diff12itmp == diff12i) - dr3.begin[2] = dr3.begin[1] - linelast1 + linelast2; - else - dr3.begin[2] = dr3.begin[1] - dr12first.begin[0] + dr12first.begin[1]; - } - - if (lastDiffBlockIsDiff12) - { - dr3.end[1] = dr12last.end[0]; - dr3.end[2] = dr12last.end[1]; - if (diff10itmp == diff10i) - dr3.end[0] = dr3.end[1] - linelast1 + linelast0; - else - dr3.end[0] = dr3.end[1] - dr10last.end[0] + dr10last.end[1]; - } - else - { - dr3.end[0] = dr10last.end[1]; - dr3.end[1] = dr10last.end[0]; - if (diff12itmp == diff12i) - dr3.end[2] = dr3.end[1] - linelast1 + linelast2; - else - dr3.end[2] = dr3.end[1] - dr12last.end[0] + dr12last.end[1]; - } - - linelast0 = dr3.end[0] + 1; - linelast1 = dr3.end[1] + 1; - linelast2 = dr3.end[2] + 1; - - if (diff10i == diff10itmp) - dr3.op = OP_3RDONLY; - else if (diff12i == diff12itmp) - dr3.op = OP_1STONLY; - else - { - dr3.op = OP_2NDONLY; - for (diff02itmp = diff02i; diff02itmp < diff02count; diff02itmp++) - { - diff02.GetDiff(diff02itmp, dr02); - if (dr02.end[1] < dr3.begin[2]) - continue; - - if (dr02.begin[1] <= dr3.end[2]) - dr3.op = OP_DIFF; - break; - } - } - - if (ignore_regexp_list) - { - bool bTrivialDiff10 = true; - bool bTrivialDiff12 = true; - int i; - - for (i = diff10i; i < diff10itmp; i++) - { - diff10.GetDiff(i, dr10); - if (dr10.op != OP_TRIVIAL) - { - bTrivialDiff10 = false; - break; - } - } - - for (i = diff12i; i < diff12itmp; i++) - { - diff12.GetDiff(i, dr12); - if (dr12.op != OP_TRIVIAL) - { - bTrivialDiff12 = false; - break; - } - } - - if (bTrivialDiff10 && bTrivialDiff12) - dr3.op = OP_TRIVIAL; - } - - diff3.AddDiff(dr3); - -#ifdef _DEBUG - Debugger::message(format("left=%d,%d middle=%d,%d right=%d,%d", - dr3.begin[0], dr3.end[0], dr3.begin[1], dr3.end[1], dr3.begin[2], dr3.end[2])); - Debugger::message(format("op=%d\n",dr3.op)); -#endif - - diff3i++; - diff10i = diff10itmp; - diff12i = diff12itmp; - diff02i = diff02itmp; - } - return diff3i; -} diff --git a/Src/DiffWrapper.h b/Src/DiffWrapper.h index c56d8d3e4..fbba7892f 100644 --- a/Src/DiffWrapper.h +++ b/Src/DiffWrapper.h @@ -178,7 +178,6 @@ public: void FixLastDiffRange(int nFiles, int bufferLines[], bool bMissingNL[], bool bIgnoreBlankLines); MovedLines * GetMovedLines(int index) { return m_pMovedLines[index].get(); } void SetCompareFiles(const PathContext &originalFile); - int Make3wayDiff(DiffList& diff3, DiffList& diff02, DiffList& diff10, DiffList& diff21); void WritePatchFileHeader(enum output_style output_style, bool bAppendFiles); void WritePatchFileTerminator(enum output_style output_style); void SetFilterList(const String& filterStr); diff --git a/Src/Merge.vcxproj b/Src/Merge.vcxproj index 30acf287b..7c7334e3e 100644 --- a/Src/Merge.vcxproj +++ b/Src/Merge.vcxproj @@ -8645,6 +8645,7 @@ + diff --git a/Src/Merge.vcxproj.filters b/Src/Merge.vcxproj.filters index 12008c8f0..5cea36b35 100644 --- a/Src/Merge.vcxproj.filters +++ b/Src/Merge.vcxproj.filters @@ -1368,6 +1368,9 @@ GUI\Header Files + + Header Files + diff --git a/Src/stringdiffs.cpp b/Src/stringdiffs.cpp index bfc3105a6..3307118a5 100644 --- a/Src/stringdiffs.cpp +++ b/Src/stringdiffs.cpp @@ -16,6 +16,7 @@ #include "stringdiffs.h" #include "CompareOptions.h" #include "stringdiffsi.h" +#include "Diff3.h" using std::vector; @@ -33,8 +34,6 @@ sd_findsyn(wdiff* pDiff, const String & str1, const String & str2, int &begin1, int &begin2, int &end1, int &end2, bool equal, int func, int &s1,int &e1,int &s2,int &e2); -static int make3wayDiff(std::vector &diff3, std::vector &diff10, std::vector &diff12); - void sd_Init() { BreakChars = &BreakCharDefaults[0]; @@ -152,23 +151,27 @@ sd_ComputeWordDiffs(int nFiles, const String str[3], } else { - std::vector diffs10, diffs12; + std::vector diffs10, diffs12, diffs02; stringdiffs sdiffs10(str[1], str[0], case_sensitive, whitespace, breakType, &diffs10); stringdiffs sdiffs12(str[1], str[2], case_sensitive, whitespace, breakType, &diffs12); + stringdiffs sdiffs02(str[0], str[2], case_sensitive, whitespace, breakType, &diffs02); // Hash all words in both lines and then compare them word by word // storing differences into m_wdiffs sdiffs10.BuildWordDiffList(); sdiffs12.BuildWordDiffList(); + sdiffs02.BuildWordDiffList(); if (byte_level) { sdiffs10.wordLevelToByteLevel(); sdiffs12.wordLevelToByteLevel(); + sdiffs02.wordLevelToByteLevel(); } // Now copy m_wdiffs into caller-supplied m_pDiffs (coalescing adjacents if possible) sdiffs10.PopulateDiffs(); sdiffs12.PopulateDiffs(); + sdiffs02.PopulateDiffs(); - make3wayDiff(*pDiffs, diffs10, diffs12); + Make3wayDiff(*pDiffs, diffs10, diffs12, diffs02, false); } } } @@ -2094,195 +2097,3 @@ bool IsSide1Empty(std::vector worddiffs, int nLineLength) return (worddiffs[0].end[1] == -1 && worddiffs[0].begin[0] == 0 && worddiffs[0].end[0] + 1 == nLineLength); } - - -/* diff3 algorithm. It is almost the same as GNU diff3's algorithm */ -static int make3wayDiff(std::vector &diff3, std::vector &diff10, std::vector &diff12) -{ - int diff10count = diff10.size(); - int diff12count = diff12.size(); - - int diff10i = 0; - int diff12i = 0; - int diff3i = 0; - - int diff10itmp; - int diff12itmp; - - bool lastDiffBlockIsDiff12; - bool firstDiffBlockIsDiff12; - - wdiff dr3, dr10, dr12, dr10first, dr10last, dr12first, dr12last; - std::vector diff3tmp; - - int linelast0 = 0; - int linelast1 = 0; - int linelast2 = 0; - - for (;;) - { - if (diff10i >= diff10count && diff12i >= diff12count) - break; - - /* - * merge overlapped diff blocks - * diff10 is diff blocks between file1 and file0. - * diff12 is diff blocks between file1 and file2. - * - * diff12 - * diff10 diff3 - * |~~~| |~~~| - * firstDiffBlock | | | | - * | | |~~~| | | - * |___| | | | | - * | | -> | | - * |~~~| |___| | | - * lastDiffBlock | | | | - * |___| |___| - */ - - if (diff10i >= diff10count && diff12i < diff12count) - { - dr12first = diff12.at(diff12i); - dr12last = dr12first; - firstDiffBlockIsDiff12 = true; - } - else if (diff10i < diff10count && diff12i >= diff12count) - { - dr10first = diff10.at(diff10i); - dr10last = dr10first; - firstDiffBlockIsDiff12 = false; - } - else - { - dr10first = diff10.at(diff10i); - dr12first = diff12.at(diff12i); - dr10last = dr10first; - dr12last = dr12first; - - if (dr12first.begin[0] <= dr10first.begin[0]) - firstDiffBlockIsDiff12 = true; - else - firstDiffBlockIsDiff12 = false; - } - lastDiffBlockIsDiff12 = firstDiffBlockIsDiff12; - - diff10itmp = diff10i; - diff12itmp = diff12i; - for (;;) - { - if (diff10itmp >= diff10count || diff12itmp >= diff12count) - break; - - dr10 = diff10.at(diff10itmp); - dr12 = diff12.at(diff12itmp); - - if (dr10.end[0] == dr12.end[0]) - { - diff10itmp++; - lastDiffBlockIsDiff12 = true; - - dr10last = dr10; - dr12last = dr12; - break; - } - - if (lastDiffBlockIsDiff12) - { - if (dr12.end[0] + 1 < dr10.begin[0]) - break; - } - else - { - if (dr10.end[0] + 1 < dr12.begin[0]) - break; - } - - if (dr12.end[0] > dr10.end[0]) - { - diff10itmp++; - lastDiffBlockIsDiff12 = true; - } - else - { - diff12itmp++; - lastDiffBlockIsDiff12 = false; - } - - dr10last = dr10; - dr12last = dr12; - } - - if (lastDiffBlockIsDiff12) - diff12itmp++; - else - diff10itmp++; - - if (firstDiffBlockIsDiff12) - { - dr3.begin[1] = dr12first.begin[0]; - dr3.begin[2] = dr12first.begin[1]; - if (diff10itmp == diff10i) - dr3.begin[0] = dr3.begin[1] - linelast1 + linelast0; - else - dr3.begin[0] = dr3.begin[1] - dr10first.begin[0] + dr10first.begin[1]; - } - else - { - dr3.begin[0] = dr10first.begin[1]; - dr3.begin[1] = dr10first.begin[0]; - if (diff12itmp == diff12i) - dr3.begin[2] = dr3.begin[1] - linelast1 + linelast2; - else - dr3.begin[2] = dr3.begin[1] - dr12first.begin[0] + dr12first.begin[1]; - } - - if (lastDiffBlockIsDiff12) - { - dr3.end[1] = dr12last.end[0]; - dr3.end[2] = dr12last.end[1]; - if (diff10itmp == diff10i) - dr3.end[0] = dr3.end[1] - linelast1 + linelast0; - else - dr3.end[0] = dr3.end[1] - dr10last.end[0] + dr10last.end[1]; - } - else - { - dr3.end[0] = dr10last.end[1]; - dr3.end[1] = dr10last.end[0]; - if (diff12itmp == diff12i) - dr3.end[2] = dr3.end[1] - linelast1 + linelast2; - else - dr3.end[2] = dr3.end[1] - dr12last.end[0] + dr12last.end[1]; - } - - linelast0 = dr3.end[0] + 1; - linelast1 = dr3.end[1] + 1; - linelast2 = dr3.end[2] + 1; - - diff3tmp.push_back(dr3); - -// TRACE(_T("left=%d,%d middle=%d,%d right=%d,%d\n"), -// dr3.begin[0], dr3.end[0], dr3.begin[1], dr3.end[1], dr3.begin[2], dr3.end[2]); - - diff3i++; - diff10i = diff10itmp; - diff12i = diff12itmp; - } - - for (int i = 0; i < diff3i; i++) - { - dr3 = diff3tmp.at(i); - if (i < diff3i - 1) - { - wdiff dr3next = diff3tmp.at(i + 1); - for (int j = 0; j < 3; j++) - { - if (dr3.end[j] >= dr3next.begin[j]) - dr3.end[j] = dr3next.begin[j] - 1; - } - } - diff3.push_back(dr3); - } - return diff3i; -} diff --git a/Src/stringdiffs.h b/Src/stringdiffs.h index 753691fd2..4ebbefc07 100644 --- a/Src/stringdiffs.h +++ b/Src/stringdiffs.h @@ -17,6 +17,7 @@ struct wdiff { int begin[3]; // 0-based, eg, begin[0] is from str1 int end[3]; // 0-based, eg, end[1] is from str2 + int op; wdiff(int s1=0, int e1=0, int s2=0, int e2=0, int s3=0, int e3=0) { if (s1>e1) e1=s1-1; @@ -28,6 +29,7 @@ struct wdiff { end[0] = e1; end[1] = e2; end[2] = e3; + op = -1; } wdiff(const wdiff & src) { -- 2.11.0