1 // TortoiseGitMerge - a Diff/Patch program
3 // Copyright (C) 2010-2012 - TortoiseSVN
5 // This program is free software; you can redistribute it and/or
6 // modify it under the terms of the GNU General Public License
7 // as published by the Free Software Foundation; either version 2
8 // of the License, or (at your option) any later version.
10 // This program is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU General Public License for more details.
15 // You should have received a copy of the GNU General Public License
16 // along with this program; if not, write to the Free Software Foundation,
17 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 #include "MovedBlocks.h"
26 // This file implements moved blocks detection algorithm, based
27 // on WinMerges(http:\\winmerge.org) one
35 bool IsPresent(int val
) const;
36 int GetSingle() const;
41 struct EquivalencyGroup
43 IntSet m_LinesLeft
; // equivalent lines on left pane
44 IntSet m_LinesRight
; // equivalent lines on right pane
46 bool IsPerfectMatch() const;
49 class LineToGroupMap
: public std::map
<CString
, EquivalencyGroup
*>
52 void Add(int lineno
, const CString
&line
, int nside
);
53 EquivalencyGroup
*find(const CString
&line
) const;
57 void IntSet::Add(int val
)
62 void IntSet::Remove(int val
)
67 int IntSet::Count() const
69 return (int)m_set
.size();
72 bool IntSet::IsPresent(int val
) const
74 return m_set
.find(val
) != m_set
.end();
77 int IntSet::GetSingle() const
81 return *m_set
.cbegin();
86 bool EquivalencyGroup::IsPerfectMatch() const
88 return (m_LinesLeft
.Count() == 1)&&(m_LinesRight
.Count() == 1);
91 void LineToGroupMap::Add(int lineno
, const CString
&line
, int nside
)
93 EquivalencyGroup
*pGroup
= NULL
;
94 auto it
= __super::find(line
);
97 pGroup
= new EquivalencyGroup
;
98 insert(std::pair
<CString
, EquivalencyGroup
*>(line
, pGroup
));
104 pGroup
->m_LinesRight
.Add(lineno
);
108 pGroup
->m_LinesLeft
.Add(lineno
);
112 EquivalencyGroup
*LineToGroupMap::find(const CString
&line
) const
114 EquivalencyGroup
*pGroup
= NULL
;
115 auto it
= __super::find(line
);
121 LineToGroupMap::~LineToGroupMap()
123 for (auto it
= cbegin(); it
!= cend(); ++it
)
129 tsvn_svn_diff_t_extension
* CreateDiffExtension(svn_diff_t
* base
, apr_pool_t
* pool
)
131 tsvn_svn_diff_t_extension
* ext
= (tsvn_svn_diff_t_extension
*)apr_palloc(pool
, sizeof(tsvn_svn_diff_t_extension
));
134 ext
->moved_from
= -1;
139 void AdjustExistingAndTail(svn_diff_t
* tempdiff
, tsvn_svn_diff_t_extension
*& existing
, tsvn_svn_diff_t_extension
*& tail
)
141 if(existing
&& existing
->base
== tempdiff
)
143 if(tail
&& tail
!= existing
)
145 tail
->next
= existing
;
148 existing
= existing
->next
;
152 CString
GetTrimmedString(const CString
& s1
, DWORD dwIgnoreWS
)
161 else if(dwIgnoreWS
== 2)
162 return CString(s1
).TrimLeft(_T(" \t"));
163 return CString(s1
).TrimRight(_T(" \t"));
166 EquivalencyGroup
* ExtractGroup(const LineToGroupMap
& map
, const CString
& line
, DWORD dwIgnoreWS
)
169 return map
.find(GetTrimmedString(line
, dwIgnoreWS
));
170 return map
.find(line
);
173 tsvn_svn_diff_t_extension
* CDiffData::MovedBlocksDetect(svn_diff_t
* diffYourBase
, DWORD dwIgnoreWS
, apr_pool_t
* pool
)
176 tsvn_svn_diff_t_extension
* head
= NULL
;
177 tsvn_svn_diff_t_extension
* tail
= NULL
;
178 svn_diff_t
* tempdiff
= diffYourBase
;
181 for(;tempdiff
; tempdiff
= tempdiff
->next
) // fill map
183 if(tempdiff
->type
!= svn_diff__type_diff_modified
)
186 baseLine
= (LONG
)tempdiff
->original_start
;
187 for(int i
= 0; i
< tempdiff
->original_length
; ++i
, ++baseLine
)
189 const CString
&sCurrentBaseLine
= m_arBaseFile
.GetAt(baseLine
);
191 map
.Add(baseLine
, GetTrimmedString(sCurrentBaseLine
, dwIgnoreWS
), 0);
193 map
.Add(baseLine
, sCurrentBaseLine
, 0);
195 yourLine
= (LONG
)tempdiff
->modified_start
;
196 for(int i
= 0; i
< tempdiff
->modified_length
; ++i
, ++yourLine
)
198 const CString
&sCurrentYourLine
= m_arYourFile
.GetAt(yourLine
);
200 map
.Add(yourLine
, GetTrimmedString(sCurrentYourLine
, dwIgnoreWS
), 1);
202 map
.Add(yourLine
, sCurrentYourLine
, 1);
205 for(tempdiff
= diffYourBase
; tempdiff
; tempdiff
= tempdiff
->next
)
207 // Scan through diff blocks, finding moved sections from left side
208 // and splitting them out
209 // That is, we actually fragment diff blocks as we find moved sections
210 if(tempdiff
->type
!= svn_diff__type_diff_modified
)
213 EquivalencyGroup
* pGroup
= NULL
;
216 for(i
= (int)tempdiff
->original_start
; (i
- tempdiff
->original_start
)< tempdiff
->original_length
; ++i
)
218 EquivalencyGroup
* group
= ExtractGroup(map
, m_arBaseFile
.GetAt(i
), dwIgnoreWS
);
219 if(group
->IsPerfectMatch())
225 if(!pGroup
) // if no match
228 int j
= pGroup
->m_LinesRight
.GetSingle();
229 // Ok, now our moved block is the single line (i, j)
231 // extend moved block upward as far as possible
234 for(; (i1
>= tempdiff
->original_start
) && (j1
>=0) && (i1
>=0); --i1
, --j1
)
236 EquivalencyGroup
* pGroup0
= ExtractGroup(map
, m_arBaseFile
.GetAt(i1
), dwIgnoreWS
);
237 EquivalencyGroup
* pGroup1
= ExtractGroup(map
, m_arYourFile
.GetAt(j1
), dwIgnoreWS
);
238 if(pGroup1
!= pGroup0
)
240 pGroup0
->m_LinesLeft
.Remove(i1
);
241 pGroup1
->m_LinesRight
.Remove(j1
);
245 // Ok, now our moved block is (i1..i, j1..j)
247 // extend moved block downward as far as possible
251 for(; ((i2
-tempdiff
->original_start
) < tempdiff
->original_length
)&&(j2
>=0); ++i2
, ++j2
)
253 if(i2
>= m_arBaseFile
.GetCount() || j2
>= m_arYourFile
.GetCount())
255 EquivalencyGroup
* pGroup0
= ExtractGroup(map
, m_arBaseFile
.GetAt(i2
), dwIgnoreWS
);
256 EquivalencyGroup
* pGroup1
= ExtractGroup(map
, m_arYourFile
.GetAt(j2
), dwIgnoreWS
);
257 if(pGroup1
!= pGroup0
)
259 pGroup0
->m_LinesLeft
.Remove(i2
);
260 pGroup1
->m_LinesRight
.Remove(j2
);
264 // Ok, now our moved block is (i1..i2,j1..j2)
265 tsvn_svn_diff_t_extension
* newTail
= CreateDiffExtension(tempdiff
, pool
);
273 tail
->next
= newTail
;
277 int prefix
= i1
- (int)tempdiff
->original_start
;
280 // break tempdiff (current change) into two pieces
281 // first part is the prefix, before the moved part
282 // that stays in tempdiff
283 // second part is the moved part & anything after it
284 // that goes in newob
285 // leave the left side (tempdiff->original_length) on tempdiff
286 // so no right side on newob
287 // newob will be the moved part only, later after we split off any suffix from it
288 svn_diff_t
* newob
= (svn_diff_t
*)apr_palloc(pool
, sizeof(svn_diff_t
));
289 memset(newob
, 0, sizeof(*newob
));
292 newob
->type
= svn_diff__type_diff_modified
;
293 newob
->original_start
= i1
;
294 newob
->modified_start
= tempdiff
->modified_start
+ tempdiff
->modified_length
;
295 newob
->modified_length
= 0;
296 newob
->original_length
= tempdiff
->original_length
- prefix
;
297 newob
->next
= tempdiff
->next
;
299 tempdiff
->original_length
= prefix
;
300 tempdiff
->next
= newob
;
302 // now make tempdiff point to the moved part (& any suffix)
308 apr_off_t suffix
= (tempdiff
->original_length
) - (i2
- (tempdiff
->original_start
)) - 1;
311 // break off any suffix from tempdiff
312 // newob will be the suffix, and will get all the right side
313 svn_diff_t
* newob
= (svn_diff_t
*) apr_palloc(pool
, sizeof (*newob
));
314 memset(newob
, 0, sizeof(*newob
));
315 newob
->type
= svn_diff__type_diff_modified
;
317 newob
->original_start
= i2
+ 1;
318 newob
->modified_start
= tempdiff
->modified_start
;
319 newob
->modified_length
= tempdiff
->modified_length
;
320 newob
->original_length
= suffix
;
321 newob
->next
= tempdiff
->next
;
323 tempdiff
->modified_length
= 0;
324 tempdiff
->original_length
-= suffix
;
325 tempdiff
->next
= newob
;
328 // Scan through diff blocks, finding moved sections from right side
329 // and splitting them out
330 // That is, we actually fragment diff blocks as we find moved sections
331 tsvn_svn_diff_t_extension
* existing
= head
;
333 for(tempdiff
= diffYourBase
; tempdiff
; tempdiff
= tempdiff
->next
)
335 // scan down block for a match
336 if(tempdiff
->type
!= svn_diff__type_diff_modified
)
339 EquivalencyGroup
* pGroup
= NULL
;
341 for(j
= (int)tempdiff
->modified_start
; (j
- tempdiff
->modified_start
) < tempdiff
->modified_length
; ++j
)
343 EquivalencyGroup
* group
= ExtractGroup(map
, m_arYourFile
.GetAt(j
), dwIgnoreWS
);
344 if(group
->IsPerfectMatch())
351 // if no match, go to next diff block
354 AdjustExistingAndTail(tempdiff
, existing
, tail
);
359 int i
= pGroup
->m_LinesLeft
.GetSingle();
362 // Ok, now our moved block is the single line (i,j)
364 // extend moved block upward as far as possible
367 for ( ; (j1
>=tempdiff
->modified_start
) && (j1
>=0) && (i1
>=0); --i1
, --j1
)
369 EquivalencyGroup
* pGroup0
= ExtractGroup(map
, m_arBaseFile
.GetAt(i1
), dwIgnoreWS
);
370 EquivalencyGroup
* pGroup1
= ExtractGroup(map
, m_arYourFile
.GetAt(j1
), dwIgnoreWS
);
371 if (pGroup0
!= pGroup1
)
373 pGroup0
->m_LinesLeft
.Remove(i1
);
374 pGroup1
->m_LinesRight
.Remove(j1
);
378 // Ok, now our moved block is (i1..i,j1..j)
380 // extend moved block downward as far as possible
383 for ( ; (j2
-(tempdiff
->modified_start
) < tempdiff
->modified_length
) && (i2
>=0); ++i2
,++j2
)
385 if(i2
>= m_arBaseFile
.GetCount() || j2
>= m_arYourFile
.GetCount())
387 EquivalencyGroup
* pGroup0
= ExtractGroup(map
, m_arBaseFile
.GetAt(i2
), dwIgnoreWS
);
388 EquivalencyGroup
* pGroup1
= ExtractGroup(map
, m_arYourFile
.GetAt(j2
), dwIgnoreWS
);
389 if (pGroup0
!= pGroup1
)
391 pGroup0
->m_LinesLeft
.Remove(i2
);
392 pGroup1
->m_LinesRight
.Remove(j2
);
396 // Ok, now our moved block is (i1..i2,j1..j2)
397 tsvn_svn_diff_t_extension
* newTail
= NULL
;
398 if(existing
&& existing
->base
== tempdiff
)
404 newTail
= CreateDiffExtension(tempdiff
, pool
);
411 newTail
->next
= tail
->next
;
412 tail
->next
= newTail
;
417 apr_off_t prefix
= j1
- (tempdiff
->modified_start
);
420 // break tempdiff (current change) into two pieces
421 // first part is the prefix, before the moved part
422 // that stays in tempdiff
423 // second part is the moved part & anything after it
424 // that goes in newob
425 // leave the left side (tempdiff->original_length) on tempdiff
426 // so no right side on newob
427 // newob will be the moved part only, later after we split off any suffix from it
428 svn_diff_t
* newob
= (svn_diff_t
*) apr_palloc(pool
, sizeof (*newob
));
429 memset(newob
, 0, sizeof(*newob
));
430 newob
->type
= svn_diff__type_diff_modified
;
432 if(existing
== newTail
)
434 newTail
= CreateDiffExtension(newob
, pool
);
435 newTail
->next
= tail
->next
;
436 tail
->next
= newTail
;
440 newob
->original_start
= tempdiff
->original_start
+ tempdiff
->original_length
;
441 newob
->modified_start
= j1
;
442 newob
->modified_length
= tempdiff
->modified_length
- prefix
;
443 newob
->original_length
= 0;
444 newob
->next
= tempdiff
->next
;
446 tempdiff
->modified_length
= prefix
;
447 tempdiff
->next
= newob
;
449 // now make tempdiff point to the moved part (& any suffix)
452 // now tempdiff points to a moved diff chunk with no prefix, but maybe a suffix
454 tail
->moved_from
= i1
;
456 apr_off_t suffix
= (tempdiff
->modified_length
) - (j2
-(tempdiff
->modified_start
)) - 1;
459 // break off any suffix from tempdiff
460 // newob will be the suffix, and will get all the left side
461 svn_diff_t
* newob
= (svn_diff_t
*) apr_palloc(pool
, sizeof (*newob
));
462 memset(newob
, 0, sizeof(*newob
));
463 tsvn_svn_diff_t_extension
* eNewOb
= CreateDiffExtension(newob
, pool
);
465 newob
->type
= svn_diff__type_diff_modified
;
466 newob
->original_start
= tempdiff
->original_start
;
467 newob
->modified_start
= j2
+1;
468 newob
->modified_length
= suffix
;
469 newob
->original_length
= tempdiff
->original_length
;
470 newob
->next
= tempdiff
->next
;
471 eNewOb
->moved_from
= -1;
472 eNewOb
->moved_to
= tail
->moved_to
;
474 tempdiff
->modified_length
-= suffix
;
475 tempdiff
->original_length
= 0;
477 tempdiff
->next
= newob
;
478 eNewOb
->next
= tail
->next
;
480 existing
= tail
= eNewOb
;
482 AdjustExistingAndTail(tempdiff
, existing
, tail
);