1 // TortoiseGitMerge - a Diff/Patch program
3 // Copyright (C) 2010-2013 - 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 if (m_arBaseFile
.GetCount() <= (baseLine
+tempdiff
->original_length
))
189 for(int i
= 0; i
< tempdiff
->original_length
; ++i
, ++baseLine
)
191 const CString
&sCurrentBaseLine
= m_arBaseFile
.GetAt(baseLine
);
193 map
.Add(baseLine
, GetTrimmedString(sCurrentBaseLine
, dwIgnoreWS
), 0);
195 map
.Add(baseLine
, sCurrentBaseLine
, 0);
197 yourLine
= (LONG
)tempdiff
->modified_start
;
198 if (m_arYourFile
.GetCount() <= (yourLine
+tempdiff
->modified_length
))
200 for(int i
= 0; i
< tempdiff
->modified_length
; ++i
, ++yourLine
)
202 const CString
&sCurrentYourLine
= m_arYourFile
.GetAt(yourLine
);
204 map
.Add(yourLine
, GetTrimmedString(sCurrentYourLine
, dwIgnoreWS
), 1);
206 map
.Add(yourLine
, sCurrentYourLine
, 1);
209 for(tempdiff
= diffYourBase
; tempdiff
; tempdiff
= tempdiff
->next
)
211 // Scan through diff blocks, finding moved sections from left side
212 // and splitting them out
213 // That is, we actually fragment diff blocks as we find moved sections
214 if(tempdiff
->type
!= svn_diff__type_diff_modified
)
217 EquivalencyGroup
* pGroup
= NULL
;
220 for(i
= (int)tempdiff
->original_start
; (i
- tempdiff
->original_start
)< tempdiff
->original_length
; ++i
)
222 EquivalencyGroup
* group
= ExtractGroup(map
, m_arBaseFile
.GetAt(i
), dwIgnoreWS
);
223 if(group
->IsPerfectMatch())
229 if(!pGroup
) // if no match
232 int j
= pGroup
->m_LinesRight
.GetSingle();
233 // Ok, now our moved block is the single line (i, j)
235 // extend moved block upward as far as possible
238 for(; (i1
>= tempdiff
->original_start
) && (j1
>=0) && (i1
>=0); --i1
, --j1
)
240 EquivalencyGroup
* pGroup0
= ExtractGroup(map
, m_arBaseFile
.GetAt(i1
), dwIgnoreWS
);
241 EquivalencyGroup
* pGroup1
= ExtractGroup(map
, m_arYourFile
.GetAt(j1
), dwIgnoreWS
);
242 if(pGroup1
!= pGroup0
)
244 pGroup0
->m_LinesLeft
.Remove(i1
);
245 pGroup1
->m_LinesRight
.Remove(j1
);
249 // Ok, now our moved block is (i1..i, j1..j)
251 // extend moved block downward as far as possible
255 for(; ((i2
-tempdiff
->original_start
) < tempdiff
->original_length
)&&(j2
>=0); ++i2
, ++j2
)
257 if(i2
>= m_arBaseFile
.GetCount() || j2
>= m_arYourFile
.GetCount())
259 EquivalencyGroup
* pGroup0
= ExtractGroup(map
, m_arBaseFile
.GetAt(i2
), dwIgnoreWS
);
260 EquivalencyGroup
* pGroup1
= ExtractGroup(map
, m_arYourFile
.GetAt(j2
), dwIgnoreWS
);
261 if(pGroup1
!= pGroup0
)
263 pGroup0
->m_LinesLeft
.Remove(i2
);
264 pGroup1
->m_LinesRight
.Remove(j2
);
268 // Ok, now our moved block is (i1..i2,j1..j2)
269 tsvn_svn_diff_t_extension
* newTail
= CreateDiffExtension(tempdiff
, pool
);
277 tail
->next
= newTail
;
281 int prefix
= i1
- (int)tempdiff
->original_start
;
284 // break tempdiff (current change) into two pieces
285 // first part is the prefix, before the moved part
286 // that stays in tempdiff
287 // second part is the moved part & anything after it
288 // that goes in newob
289 // leave the left side (tempdiff->original_length) on tempdiff
290 // so no right side on newob
291 // newob will be the moved part only, later after we split off any suffix from it
292 svn_diff_t
* newob
= (svn_diff_t
*)apr_palloc(pool
, sizeof(svn_diff_t
));
293 memset(newob
, 0, sizeof(*newob
));
296 newob
->type
= svn_diff__type_diff_modified
;
297 newob
->original_start
= i1
;
298 newob
->modified_start
= tempdiff
->modified_start
+ tempdiff
->modified_length
;
299 newob
->modified_length
= 0;
300 newob
->original_length
= tempdiff
->original_length
- prefix
;
301 newob
->next
= tempdiff
->next
;
303 tempdiff
->original_length
= prefix
;
304 tempdiff
->next
= newob
;
306 // now make tempdiff point to the moved part (& any suffix)
312 apr_off_t suffix
= (tempdiff
->original_length
) - (i2
- (tempdiff
->original_start
)) - 1;
315 // break off any suffix from tempdiff
316 // newob will be the suffix, and will get all the right side
317 svn_diff_t
* newob
= (svn_diff_t
*) apr_palloc(pool
, sizeof (*newob
));
318 memset(newob
, 0, sizeof(*newob
));
319 newob
->type
= svn_diff__type_diff_modified
;
321 newob
->original_start
= i2
+ 1;
322 newob
->modified_start
= tempdiff
->modified_start
;
323 newob
->modified_length
= tempdiff
->modified_length
;
324 newob
->original_length
= suffix
;
325 newob
->next
= tempdiff
->next
;
327 tempdiff
->modified_length
= 0;
328 tempdiff
->original_length
-= suffix
;
329 tempdiff
->next
= newob
;
332 // Scan through diff blocks, finding moved sections from right side
333 // and splitting them out
334 // That is, we actually fragment diff blocks as we find moved sections
335 tsvn_svn_diff_t_extension
* existing
= head
;
337 for(tempdiff
= diffYourBase
; tempdiff
; tempdiff
= tempdiff
->next
)
339 // scan down block for a match
340 if(tempdiff
->type
!= svn_diff__type_diff_modified
)
343 EquivalencyGroup
* pGroup
= NULL
;
345 for(j
= (int)tempdiff
->modified_start
; (j
- tempdiff
->modified_start
) < tempdiff
->modified_length
; ++j
)
347 EquivalencyGroup
* group
= ExtractGroup(map
, m_arYourFile
.GetAt(j
), dwIgnoreWS
);
348 if(group
->IsPerfectMatch())
355 // if no match, go to next diff block
358 AdjustExistingAndTail(tempdiff
, existing
, tail
);
363 int i
= pGroup
->m_LinesLeft
.GetSingle();
366 // Ok, now our moved block is the single line (i,j)
368 // extend moved block upward as far as possible
371 for ( ; (j1
>=tempdiff
->modified_start
) && (j1
>=0) && (i1
>=0); --i1
, --j1
)
373 EquivalencyGroup
* pGroup0
= ExtractGroup(map
, m_arBaseFile
.GetAt(i1
), dwIgnoreWS
);
374 EquivalencyGroup
* pGroup1
= ExtractGroup(map
, m_arYourFile
.GetAt(j1
), dwIgnoreWS
);
375 if (pGroup0
!= pGroup1
)
377 pGroup0
->m_LinesLeft
.Remove(i1
);
378 pGroup1
->m_LinesRight
.Remove(j1
);
382 // Ok, now our moved block is (i1..i,j1..j)
384 // extend moved block downward as far as possible
387 for ( ; (j2
-(tempdiff
->modified_start
) < tempdiff
->modified_length
) && (i2
>=0); ++i2
,++j2
)
389 if(i2
>= m_arBaseFile
.GetCount() || j2
>= m_arYourFile
.GetCount())
391 EquivalencyGroup
* pGroup0
= ExtractGroup(map
, m_arBaseFile
.GetAt(i2
), dwIgnoreWS
);
392 EquivalencyGroup
* pGroup1
= ExtractGroup(map
, m_arYourFile
.GetAt(j2
), dwIgnoreWS
);
393 if (pGroup0
!= pGroup1
)
395 pGroup0
->m_LinesLeft
.Remove(i2
);
396 pGroup1
->m_LinesRight
.Remove(j2
);
400 // Ok, now our moved block is (i1..i2,j1..j2)
401 tsvn_svn_diff_t_extension
* newTail
= NULL
;
402 if(existing
&& existing
->base
== tempdiff
)
408 newTail
= CreateDiffExtension(tempdiff
, pool
);
415 newTail
->next
= tail
->next
;
416 tail
->next
= newTail
;
421 apr_off_t prefix
= j1
- (tempdiff
->modified_start
);
424 // break tempdiff (current change) into two pieces
425 // first part is the prefix, before the moved part
426 // that stays in tempdiff
427 // second part is the moved part & anything after it
428 // that goes in newob
429 // leave the left side (tempdiff->original_length) on tempdiff
430 // so no right side on newob
431 // newob will be the moved part only, later after we split off any suffix from it
432 svn_diff_t
* newob
= (svn_diff_t
*) apr_palloc(pool
, sizeof (*newob
));
433 memset(newob
, 0, sizeof(*newob
));
434 newob
->type
= svn_diff__type_diff_modified
;
436 if(existing
== newTail
)
438 newTail
= CreateDiffExtension(newob
, pool
);
439 newTail
->next
= tail
->next
;
440 tail
->next
= newTail
;
444 newob
->original_start
= tempdiff
->original_start
+ tempdiff
->original_length
;
445 newob
->modified_start
= j1
;
446 newob
->modified_length
= tempdiff
->modified_length
- prefix
;
447 newob
->original_length
= 0;
448 newob
->next
= tempdiff
->next
;
450 tempdiff
->modified_length
= prefix
;
451 tempdiff
->next
= newob
;
453 // now make tempdiff point to the moved part (& any suffix)
456 // now tempdiff points to a moved diff chunk with no prefix, but maybe a suffix
458 tail
->moved_from
= i1
;
460 apr_off_t suffix
= (tempdiff
->modified_length
) - (j2
-(tempdiff
->modified_start
)) - 1;
463 // break off any suffix from tempdiff
464 // newob will be the suffix, and will get all the left side
465 svn_diff_t
* newob
= (svn_diff_t
*) apr_palloc(pool
, sizeof (*newob
));
466 memset(newob
, 0, sizeof(*newob
));
467 tsvn_svn_diff_t_extension
* eNewOb
= CreateDiffExtension(newob
, pool
);
469 newob
->type
= svn_diff__type_diff_modified
;
470 newob
->original_start
= tempdiff
->original_start
;
471 newob
->modified_start
= j2
+1;
472 newob
->modified_length
= suffix
;
473 newob
->original_length
= tempdiff
->original_length
;
474 newob
->next
= tempdiff
->next
;
475 eNewOb
->moved_from
= -1;
476 eNewOb
->moved_to
= tail
->moved_to
;
478 tempdiff
->modified_length
-= suffix
;
479 tempdiff
->original_length
= 0;
481 tempdiff
->next
= newob
;
482 eNewOb
->next
= tail
->next
;
484 existing
= tail
= eNewOb
;
486 AdjustExistingAndTail(tempdiff
, existing
, tail
);