?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
android: Update app-specific/MIME type icons
[LibreOffice.git] / sw / source / core / doc / doccomp.cxx
blob32ec6bb85aaaf105db8be6b11fcd0424e4405706
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
3 * This file is part of the LibreOffice project.
4 *
5 * This Source Code Form is subject to the terms of the Mozilla Public
6 * License, v. 2.0. If a copy of the MPL was not distributed with this
7 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 *
9 * This file incorporates work covered by the following license notice:
10 *
11 * Licensed to the Apache Software Foundation (ASF) under one or more
12 * contributor license agreements. See the NOTICE file distributed
13 * with this work for additional information regarding copyright
14 * ownership. The ASF licenses this file to you under the Apache
15 * License, Version 2.0 (the "License"); you may not use this file
16 * except in compliance with the License. You may obtain a copy of
17 * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 */
19
20 #include <sal/config.h>
21
22 #include <rtl/ustrbuf.hxx>
23 #include <o3tl/safeint.hxx>
24 #include <osl/diagnose.h>
25 #include <rtl/character.hxx>
26 #include <swmodule.hxx>
27 #include <doc.hxx>
28 #include <IDocumentUndoRedo.hxx>
29 #include <DocumentContentOperationsManager.hxx>
30 #include <IDocumentRedlineAccess.hxx>
31 #include <IDocumentState.hxx>
32 #include <docary.hxx>
33 #include <pam.hxx>
34 #include <ndtxt.hxx>
35 #include <redline.hxx>
36 #include <UndoRedline.hxx>
37 #include <section.hxx>
38 #include <tox.hxx>
39 #include <docsh.hxx>
40 #include <fmtcntnt.hxx>
41 #include <modcfg.hxx>
42 #include <frameformats.hxx>
43
44 #include <com/sun/star/document/XDocumentPropertiesSupplier.hpp>
45 #include <com/sun/star/document/XDocumentProperties.hpp>
46 #include <com/sun/star/frame/XModel.hpp>
47
48 #include <cstddef>
49 #include <memory>
50 #include <type_traits>
51 #include <vector>
52
53 using namespace ::com::sun::star;
54
55 using std::vector;
56
57 namespace {
58
59 class SwCompareLine final
60 {
61 const SwNode* m_pNode;
62 public:
63 explicit SwCompareLine( const SwNode& rNd ) : m_pNode( &rNd ) {}
64 SwCompareLine() : m_pNode( nullptr ) {}
65
66 sal_uLong GetHashValue() const;
67 bool Compare( const SwCompareLine& rLine ) const;
68
69 static sal_uLong GetTextNodeHashValue( const SwTextNode& rNd, sal_uLong nVal );
70 static bool CompareNode( const SwNode& rDstNd, const SwNode& rSrcNd );
71 static bool CompareTextNd( const SwTextNode& rDstNd,
72 const SwTextNode& rSrcNd );
73
74 bool ChangesInLine( const SwCompareLine& rLine,
75 std::unique_ptr<SwPaM>& rpInsRing, std::unique_ptr<SwPaM>& rpDelRing ) const;
76
77 const SwNode& GetNode() const { return *m_pNode; }
78
79 const SwNode& GetEndNode() const;
80
81 // for debugging
82 OUString GetText() const;
83 };
84
85
86 class CompareData
87 {
88 protected:
89 SwDoc& m_rDoc;
90 private:
91 std::unique_ptr<size_t[]> m_pIndex;
92 std::unique_ptr<bool[]> m_pChangedFlag;
93
94 std::unique_ptr<SwPaM> m_pInsertRing, m_pDelRing;
95
96 static SwNodeOffset PrevIdx( const SwNode* pNd );
97 static SwNodeOffset NextIdx( const SwNode* pNd );
98
99 vector<SwCompareLine> m_aLines;
100 bool m_bRecordDiff;
101
102 // Truncate beginning and end and add all others to the LinesArray
103 void CheckRanges( CompareData& );
104
105 virtual const SwNode& GetEndOfContent() = 0;
106
107 public:
108 CompareData(SwDoc& rD, bool bRecordDiff)
109 : m_rDoc( rD )
110 , m_bRecordDiff(bRecordDiff)
111 {
112 }
113 virtual ~CompareData();
114
115 // Are there differences?
116 bool HasDiffs( const CompareData& rData ) const;
117
118 // Triggers the comparison and creation of two documents
119 void CompareLines( CompareData& rData );
120 // Display the differences - calls the methods ShowInsert and ShowDelete.
121 // These are passed the start and end line number.
122 // Displaying the actually content is to be handled by the subclass!
123 sal_uLong ShowDiffs( const CompareData& rData );
124
125 void ShowInsert( sal_uLong nStt, sal_uLong nEnd );
126 void ShowDelete( const CompareData& rData, sal_uLong nStt,
127 sal_uLong nEnd, sal_uLong nInsPos );
128 void CheckForChangesInLine( const CompareData& rData,
129 sal_uLong nStt, sal_uLong nEnd,
130 sal_uLong nThisStt, sal_uLong nThisEnd );
131
132 // Set non-ambiguous index for a line. Same lines have the same index, even in the other CompareData!
133 void SetIndex( size_t nLine, size_t nIndex );
134 size_t GetIndex( size_t nLine ) const
135 { return nLine < m_aLines.size() ? m_pIndex[ nLine ] : 0; }
136
137 // Set/get of a line has changed
138 void SetChanged( size_t nLine, bool bFlag = true );
139 bool GetChanged( size_t nLine ) const
140 {
141 return (m_pChangedFlag && nLine < m_aLines.size())
142 && m_pChangedFlag[ nLine ];
143 }
144
145 size_t GetLineCount() const { return m_aLines.size(); }
146 const SwCompareLine& GetLine( size_t nLine ) const
147 { return m_aLines[ nLine ]; }
148 void InsertLine( SwCompareLine aLine )
149 { m_aLines.push_back( aLine ); }
150
151 void SetRedlinesToDoc( bool bUseDocInfo );
152 };
153
154 class CompareMainText : public CompareData
155 {
156 public:
157 CompareMainText(SwDoc &rD, bool bRecordDiff)
158 : CompareData(rD, bRecordDiff)
159 {
160 }
161
162 virtual const SwNode& GetEndOfContent() override
163 {
164 return m_rDoc.GetNodes().GetEndOfContent();
165 }
166 };
167
168 class CompareFrameFormatText : public CompareData
169 {
170 const SwNodeIndex &m_rIndex;
171 public:
172 CompareFrameFormatText(SwDoc &rD, const SwNodeIndex &rIndex)
173 : CompareData(rD, true/*bRecordDiff*/)
174 , m_rIndex(rIndex)
175 {
176 }
177
178 virtual const SwNode& GetEndOfContent() override
179 {
180 return *m_rIndex.GetNode().EndOfSectionNode();
181 }
182 };
183
184 class Hash
185 {
186 struct HashData
187 {
188 sal_uLong nNext, nHash;
189 SwCompareLine aLine;
190
191 HashData()
192 : nNext( 0 ), nHash( 0 ) {}
193 };
194
195 std::unique_ptr<sal_uLong[]> m_pHashArr;
196 std::unique_ptr<HashData[]> m_pDataArr;
197 sal_uLong m_nCount, m_nPrime;
198
199 public:
200 explicit Hash( sal_uLong nSize );
201
202 void CalcHashValue( CompareData& rData );
203
204 sal_uLong GetCount() const { return m_nCount; }
205 };
206
207 class Compare
208 {
209 public:
210 class MovedData
211 {
212 std::unique_ptr<sal_uLong[]> m_pIndex;
213 std::unique_ptr<sal_uLong[]> m_pLineNum;
214 sal_uLong m_nCount;
215
216 public:
217 MovedData( CompareData& rData, const char* pDiscard );
218
219 sal_uLong GetIndex( sal_uLong n ) const { return m_pIndex[ n ]; }
220 sal_uLong GetLineNum( sal_uLong n ) const { return m_pLineNum[ n ]; }
221 sal_uLong GetCount() const { return m_nCount; }
222 };
223
224 private:
225 /// Look for the moved lines
226 class CompareSequence
227 {
228 CompareData &m_rData1, &m_rData2;
229 const MovedData &m_rMoved1, &m_rMoved2;
230 std::unique_ptr<tools::Long[]> m_pMemory;
231 tools::Long *m_pFDiag, *m_pBDiag;
232
233 void Compare( sal_uLong nStt1, sal_uLong nEnd1, sal_uLong nStt2, sal_uLong nEnd2 );
234 sal_uLong CheckDiag( sal_uLong nStt1, sal_uLong nEnd1,
235 sal_uLong nStt2, sal_uLong nEnd2, sal_uLong* pCost );
236 public:
237 CompareSequence( CompareData& rD1, CompareData& rD2,
238 const MovedData& rMD1, const MovedData& rMD2 );
239 };
240
241 static void CountDifference( const CompareData& rData, sal_uLong* pCounts );
242 static void SetDiscard( const CompareData& rData,
243 char* pDiscard, const sal_uLong* pCounts );
244 static void CheckDiscard( sal_uLong nLen, char* pDiscard );
245 static void ShiftBoundaries( CompareData& rData1, CompareData& rData2 );
246
247 public:
248 Compare( sal_uLong nDiff, CompareData& rData1, CompareData& rData2 );
249 };
250
251 class ArrayComparator
252 {
253 public:
254 virtual bool Compare( int nIdx1, int nIdx2 ) const = 0;
255 virtual int GetLen1() const = 0;
256 virtual int GetLen2() const = 0;
257 virtual ~ArrayComparator() {}
258 };
259
260 /// Consider two lines equal if similar enough (e.g. look like different
261 /// versions of the same paragraph)
262 class LineArrayComparator : public ArrayComparator
263 {
264 private:
265 int m_nLen1, m_nLen2;
266 const CompareData &m_rData1, &m_rData2;
267 int m_nFirst1, m_nFirst2;
268
269 public:
270 LineArrayComparator( const CompareData &rD1, const CompareData &rD2,
271 int nStt1, int nEnd1, int nStt2, int nEnd2 );
272
273 virtual bool Compare( int nIdx1, int nIdx2 ) const override;
274 virtual int GetLen1() const override { return m_nLen1; }
275 virtual int GetLen2() const override { return m_nLen2; }
276 };
277
278 class WordArrayComparator : public ArrayComparator
279 {
280 private:
281 const SwTextNode *m_pTextNode1, *m_pTextNode2;
282 std::unique_ptr<int[]> m_pPos1, m_pPos2;
283 int m_nCount1, m_nCount2; // number of words
284
285 static void CalcPositions( int *pPos, const SwTextNode *pTextNd, int &nCnt );
286
287 public:
288 WordArrayComparator( const SwTextNode *pNode1, const SwTextNode *pNode2 );
289
290 virtual bool Compare( int nIdx1, int nIdx2 ) const override;
291 virtual int GetLen1() const override { return m_nCount1; }
292 virtual int GetLen2() const override { return m_nCount2; }
293 int GetCharSequence( const int *pWordLcs1, const int *pWordLcs2,
294 int *pSubseq1, int *pSubseq2, int nLcsLen );
295 };
296
297 class CharArrayComparator : public ArrayComparator
298 {
299 private:
300 const SwTextNode *m_pTextNode1, *m_pTextNode2;
301
302 public:
303 CharArrayComparator( const SwTextNode *pNode1, const SwTextNode *pNode2 )
304 : m_pTextNode1( pNode1 ), m_pTextNode2( pNode2 )
305 {
306 }
307
308 virtual bool Compare( int nIdx1, int nIdx2 ) const override;
309 virtual int GetLen1() const override { return m_pTextNode1->GetText().getLength(); }
310 virtual int GetLen2() const override { return m_pTextNode2->GetText().getLength(); }
311 };
312
313 /// Options set in Tools->Options->Writer->Comparison
314 struct CmpOptionsContainer
315 {
316 SwCompareMode eCmpMode;
317 int nIgnoreLen;
318 bool bUseRsid;
319 };
320
321 }
322
323 static CmpOptionsContainer CmpOptions;
324
325 namespace {
326
327 class CommonSubseq
328 {
329 private:
330 std::unique_ptr<int[]> m_pData;
331
332 protected:
333 ArrayComparator &m_rComparator;
334
335 CommonSubseq( ArrayComparator &rComparator, int nMaxSize )
336 : m_rComparator( rComparator )
337 {
338 m_pData.reset( new int[ nMaxSize ] );
339 }
340
341 int FindLCS( int *pLcs1, int *pLcs2, int nStt1,
342 int nEnd1, int nStt2, int nEnd2 );
343
344 public:
345 static int IgnoreIsolatedPieces( int *pLcs1, int *pLcs2, int nLen1, int nLen2,
346 int nLcsLen, int nPieceLen );
347 };
348
349 /// Use Hirschberg's algorithm to find LCS in linear space
350 class LgstCommonSubseq: public CommonSubseq
351 {
352 private:
353 static const int CUTOFF = 1<<20; // Stop recursion at this value
354
355 std::unique_ptr<int[]> m_pL1, m_pL2;
356 std::unique_ptr<int[]> m_pBuff1, m_pBuff2;
357
358 void FindL( int *pL, int nStt1, int nEnd1, int nStt2, int nEnd2 );
359 int HirschbergLCS( int *pLcs1, int *pLcs2, int nStt1, int nEnd1,
360 int nStt2, int nEnd2 );
361
362 public:
363 explicit LgstCommonSubseq( ArrayComparator &rComparator );
364
365 int Find( int *pSubseq1, int *pSubseq2 );
366 };
367
368 /// Find a common subsequence in linear time
369 class FastCommonSubseq: private CommonSubseq
370 {
371 private:
372 static const int CUTOFF = 2056;
373
374 int FindFastCS( int *pSeq1, int *pSeq2, int nStt1, int nEnd1,
375 int nStt2, int nEnd2 );
376
377 public:
378 explicit FastCommonSubseq( ArrayComparator &rComparator )
379 : CommonSubseq( rComparator, CUTOFF )
380 {
381 }
382
383 int Find( int *pSubseq1, int *pSubseq2 )
384 {
385 return FindFastCS( pSubseq1, pSubseq2, 0, m_rComparator.GetLen1(),
386 0, m_rComparator.GetLen2() );
387 }
388 };
389
390 }
391
392 CompareData::~CompareData()
393 {
394 if( m_pDelRing )
395 {
396 while( m_pDelRing->GetNext() != m_pDelRing.get() )
397 delete m_pDelRing->GetNext();
398 m_pDelRing.reset();
399 }
400 if( m_pInsertRing )
401 {
402 while( m_pInsertRing->GetNext() != m_pInsertRing.get() )
403 delete m_pInsertRing->GetNext();
404 m_pInsertRing.reset();
405 }
406 }
407
408 void CompareData::SetIndex( size_t nLine, size_t nIndex )
409 {
410 if( !m_pIndex )
411 {
412 m_pIndex.reset( new size_t[ m_aLines.size() ] );
413 memset( m_pIndex.get(), 0, m_aLines.size() * sizeof( size_t ) );
414 }
415 if( nLine < m_aLines.size() )
416 m_pIndex[ nLine ] = nIndex;
417 }
418
419 void CompareData::SetChanged( size_t nLine, bool bFlag )
420 {
421 if( !m_pChangedFlag )
422 {
423 m_pChangedFlag.reset( new bool[ m_aLines.size() +1 ] );
424 memset( m_pChangedFlag.get(), 0, (m_aLines.size() +1) * sizeof( bool ) );
425 }
426 if( nLine < m_aLines.size() )
427 m_pChangedFlag[ nLine ] = bFlag;
428 }
429
430 void CompareData::CompareLines( CompareData& rData )
431 {
432 CheckRanges( rData );
433
434 sal_uLong nDifferent;
435 {
436 Hash aH( GetLineCount() + rData.GetLineCount() + 1 );
437 aH.CalcHashValue( *this );
438 aH.CalcHashValue( rData );
439 nDifferent = aH.GetCount();
440 }
441 {
442 Compare aComp( nDifferent, *this, rData );
443 }
444 }
445
446 sal_uLong CompareData::ShowDiffs( const CompareData& rData )
447 {
448 sal_uLong nLen1 = rData.GetLineCount(), nLen2 = GetLineCount();
449 sal_uLong nStt1 = 0, nStt2 = 0;
450 sal_uLong nCnt = 0;
451
452 while( nStt1 < nLen1 || nStt2 < nLen2 )
453 {
454 if( rData.GetChanged( nStt1 ) || GetChanged( nStt2 ) )
455 {
456 // Find a region of different lines between two pairs of identical
457 // lines.
458 sal_uLong nSav1 = nStt1, nSav2 = nStt2;
459 while( nStt1 < nLen1 && rData.GetChanged( nStt1 )) ++nStt1;
460 while( nStt2 < nLen2 && GetChanged( nStt2 )) ++nStt2;
461
462 if (m_bRecordDiff)
463 {
464 // Check if there are changed lines (only slightly different) and
465 // compare them in detail.
466 CheckForChangesInLine( rData, nSav1, nStt1, nSav2, nStt2 );
467 }
468
469 ++nCnt;
470 }
471 ++nStt1;
472 ++nStt2;
473 }
474 return nCnt;
475 }
476
477 bool CompareData::HasDiffs( const CompareData& rData ) const
478 {
479 bool bRet = false;
480 sal_uLong nLen1 = rData.GetLineCount(), nLen2 = GetLineCount();
481 sal_uLong nStt1 = 0, nStt2 = 0;
482
483 while( nStt1 < nLen1 || nStt2 < nLen2 )
484 {
485 if( rData.GetChanged( nStt1 ) || GetChanged( nStt2 ) )
486 {
487 bRet = true;
488 break;
489 }
490 ++nStt1;
491 ++nStt2;
492 }
493 return bRet;
494 }
495
496 Hash::Hash( sal_uLong nSize )
497 : m_nCount(1)
498 {
499
500 static const sal_uLong primes[] =
501 {
502 509,
503 1021,
504 2039,
505 4093,
506 8191,
507 16381,
508 32749,
509 65521,
510 131071,
511 262139,
512 524287,
513 1048573,
514 2097143,
515 4194301,
516 8388593,
517 16777213,
518 33554393,
519 67108859, /* Preposterously large . . . */
520 134217689,
521 268435399,
522 536870909,
523 1073741789,
524 2147483647,
525 0
526 };
527 int i;
528
529 m_pDataArr.reset( new HashData[ nSize ] );
530 m_pDataArr[0].nNext = 0;
531 m_pDataArr[0].nHash = 0;
532 m_nPrime = primes[0];
533
534 for( i = 0; primes[i] < nSize / 3; i++)
535 if( !primes[i] )
536 {
537 m_pHashArr = nullptr;
538 return;
539 }
540 m_nPrime = primes[ i ];
541 m_pHashArr.reset( new sal_uLong[ m_nPrime ] );
542 memset( m_pHashArr.get(), 0, m_nPrime * sizeof( sal_uLong ) );
543 }
544
545 void Hash::CalcHashValue( CompareData& rData )
546 {
547 if( !m_pHashArr )
548 return;
549
550 for( size_t n = 0; n < rData.GetLineCount(); ++n )
551 {
552 const SwCompareLine aLine = rData.GetLine( n );
553 sal_uLong nH = aLine.GetHashValue();
554
555 sal_uLong* pFound = &m_pHashArr[ nH % m_nPrime ];
556 size_t i;
557 for( i = *pFound; ; i = m_pDataArr[i].nNext )
558 if( !i )
559 {
560 i = m_nCount++;
561 m_pDataArr[i].nNext = *pFound;
562 m_pDataArr[i].nHash = nH;
563 m_pDataArr[i].aLine = aLine;
564 *pFound = i;
565 break;
566 }
567 else if( m_pDataArr[i].nHash == nH &&
568 m_pDataArr[i].aLine.Compare( aLine ))
569 break;
570
571 rData.SetIndex( n, i );
572 }
573 }
574
575 Compare::Compare( sal_uLong nDiff, CompareData& rData1, CompareData& rData2 )
576 {
577 std::unique_ptr<MovedData> pMD1, pMD2;
578 // Look for the differing lines
579 {
580 std::unique_ptr<char[]> pDiscard1( new char[ rData1.GetLineCount() ] );
581 std::unique_ptr<char[]> pDiscard2( new char[ rData2.GetLineCount() ] );
582
583 std::unique_ptr<sal_uLong[]> pCount1(new sal_uLong[ nDiff ]);
584 std::unique_ptr<sal_uLong[]> pCount2(new sal_uLong[ nDiff ]);
585 memset( pCount1.get(), 0, nDiff * sizeof( sal_uLong ));
586 memset( pCount2.get(), 0, nDiff * sizeof( sal_uLong ));
587
588 // find indices in CompareData which have been assigned multiple times
589 CountDifference( rData1, pCount1.get() );
590 CountDifference( rData2, pCount2.get() );
591
592 // All which occur only once now have either been inserted or deleted.
593 // All which are also contained in the other one have been moved.
594 SetDiscard( rData1, pDiscard1.get(), pCount2.get() );
595 SetDiscard( rData2, pDiscard2.get(), pCount1.get() );
596
597 CheckDiscard( rData1.GetLineCount(), pDiscard1.get() );
598 CheckDiscard( rData2.GetLineCount(), pDiscard2.get() );
599
600 pMD1.reset(new MovedData( rData1, pDiscard1.get() ));
601 pMD2.reset(new MovedData( rData2, pDiscard2.get() ));
602 }
603
604 {
605 CompareSequence aTmp( rData1, rData2, *pMD1, *pMD2 );
606 }
607
608 ShiftBoundaries( rData1, rData2 );
609 }
610
611 void Compare::CountDifference( const CompareData& rData, sal_uLong* pCounts )
612 {
613 sal_uLong nLen = rData.GetLineCount();
614 for( sal_uLong n = 0; n < nLen; ++n )
615 {
616 sal_uLong nIdx = rData.GetIndex( n );
617 ++pCounts[ nIdx ];
618 }
619 }
620
621 void Compare::SetDiscard( const CompareData& rData,
622 char* pDiscard, const sal_uLong* pCounts )
623 {
624 const sal_uLong nLen = rData.GetLineCount();
625
626 // calculate Max with respect to the line count
627 sal_uLong nMax = 5;
628
629 for( sal_uLong n = nLen / 64; ( n = n >> 2 ) > 0; )
630 nMax <<= 1;
631
632 for( sal_uLong n = 0; n < nLen; ++n )
633 {
634 sal_uLong nIdx = rData.GetIndex( n );
635 if( nIdx )
636 {
637 nIdx = pCounts[ nIdx ];
638 pDiscard[ n ] = !nIdx ? 1 : nIdx > nMax ? 2 : 0;
639 }
640 else
641 pDiscard[ n ] = 0;
642 }
643 }
644
645 void Compare::CheckDiscard( sal_uLong nLen, char* pDiscard )
646 {
647 for( sal_uLong n = 0; n < nLen; ++n )
648 {
649 if( 2 == pDiscard[ n ] )
650 pDiscard[n] = 0;
651 else if( pDiscard[ n ] )
652 {
653 sal_uLong j;
654 sal_uLong length;
655 sal_uLong provisional = 0;
656
657 /* Find end of this run of discardable lines.
658 Count how many are provisionally discardable. */
659 for (j = n; j < nLen; j++)
660 {
661 if( !pDiscard[j] )
662 break;
663 if( 2 == pDiscard[j] )
664 ++provisional;
665 }
666
667 /* Cancel provisional discards at end, and shrink the run. */
668 while( j > n && 2 == pDiscard[j - 1] )
669 {
670 pDiscard[ --j ] = 0;
671 --provisional;
672 }
673
674 /* Now we have the length of a run of discardable lines
675 whose first and last are not provisional. */
676 length = j - n;
677
678 /* If 1/4 of the lines in the run are provisional,
679 cancel discarding of all provisional lines in the run. */
680 if (provisional * 4 > length)
681 {
682 while (j > n)
683 if (pDiscard[--j] == 2)
684 pDiscard[j] = 0;
685 }
686 else
687 {
688 sal_uLong consec;
689 sal_uLong minimum = 1;
690 sal_uLong tem = length / 4;
691
692 /* MINIMUM is approximate square root of LENGTH/4.
693 A subrun of two or more provisionals can stand
694 when LENGTH is at least 16.
695 A subrun of 4 or more can stand when LENGTH >= 64. */
696 while ((tem = tem >> 2) > 0)
697 minimum *= 2;
698 minimum++;
699
700 /* Cancel any subrun of MINIMUM or more provisionals
701 within the larger run. */
702 for (j = 0, consec = 0; j < length; j++)
703 if (pDiscard[n + j] != 2)
704 consec = 0;
705 else if (minimum == ++consec)
706 /* Back up to start of subrun, to cancel it all. */
707 j -= consec;
708 else if (minimum < consec)
709 pDiscard[n + j] = 0;
710
711 /* Scan from beginning of run
712 until we find 3 or more nonprovisionals in a row
713 or until the first nonprovisional at least 8 lines in.
714 Until that point, cancel any provisionals. */
715 for (j = 0, consec = 0; j < length; j++)
716 {
717 if (j >= 8 && pDiscard[n + j] == 1)
718 break;
719 if (pDiscard[n + j] == 2)
720 {
721 consec = 0;
722 pDiscard[n + j] = 0;
723 }
724 else if (pDiscard[n + j] == 0)
725 consec = 0;
726 else
727 consec++;
728 if (consec == 3)
729 break;
730 }
731
732 /* I advances to the last line of the run. */
733 n += length - 1;
734
735 /* Same thing, from end. */
736 for (j = 0, consec = 0; j < length; j++)
737 {
738 if (j >= 8 && pDiscard[n - j] == 1)
739 break;
740 if (pDiscard[n - j] == 2)
741 {
742 consec = 0;
743 pDiscard[n - j] = 0;
744 }
745 else if (pDiscard[n - j] == 0)
746 consec = 0;
747 else
748 consec++;
749 if (consec == 3)
750 break;
751 }
752 }
753 }
754 }
755 }
756
757 Compare::MovedData::MovedData( CompareData& rData, const char* pDiscard )
758 : m_nCount( 0 )
759 {
760 sal_uLong nLen = rData.GetLineCount();
761 sal_uLong n;
762
763 for( n = 0; n < nLen; ++n )
764 if( pDiscard[ n ] )
765 rData.SetChanged( n );
766 else
767 ++m_nCount;
768
769 if( m_nCount )
770 {
771 m_pIndex.reset( new sal_uLong[ m_nCount ] );
772 m_pLineNum.reset( new sal_uLong[ m_nCount ] );
773
774 for( n = 0, m_nCount = 0; n < nLen; ++n )
775 if( !pDiscard[ n ] )
776 {
777 m_pIndex[ m_nCount ] = rData.GetIndex( n );
778 m_pLineNum[ m_nCount++ ] = n;
779 }
780 }
781 }
782
783 /// Find the differing lines
784 Compare::CompareSequence::CompareSequence(
785 CompareData& rD1, CompareData& rD2,
786 const MovedData& rMD1, const MovedData& rMD2 )
787 : m_rData1( rD1 ), m_rData2( rD2 ), m_rMoved1( rMD1 ), m_rMoved2( rMD2 )
788 {
789 sal_uLong nSize = rMD1.GetCount() + rMD2.GetCount() + 3;
790 m_pMemory.reset( new tools::Long[ nSize * 2 ] );
791 m_pFDiag = m_pMemory.get() + ( rMD2.GetCount() + 1 );
792 m_pBDiag = m_pMemory.get() + ( nSize + rMD2.GetCount() + 1 );
793
794 Compare( 0, rMD1.GetCount(), 0, rMD2.GetCount() );
795 }
796
797 void Compare::CompareSequence::Compare( sal_uLong nStt1, sal_uLong nEnd1,
798 sal_uLong nStt2, sal_uLong nEnd2 )
799 {
800 /* Slide down the bottom initial diagonal. */
801 while( nStt1 < nEnd1 && nStt2 < nEnd2 &&
802 m_rMoved1.GetIndex( nStt1 ) == m_rMoved2.GetIndex( nStt2 ))
803 {
804 ++nStt1;
805 ++nStt2;
806 }
807
808 /* Slide up the top initial diagonal. */
809 while( nEnd1 > nStt1 && nEnd2 > nStt2 &&
810 m_rMoved1.GetIndex( nEnd1 - 1 ) == m_rMoved2.GetIndex( nEnd2 - 1 ))
811 {
812 --nEnd1;
813 --nEnd2;
814 }
815
816 /* Handle simple cases. */
817 if( nStt1 == nEnd1 )
818 while( nStt2 < nEnd2 )
819 m_rData2.SetChanged( m_rMoved2.GetLineNum( nStt2++ ));
820
821 else if (nStt2 == nEnd2)
822 while (nStt1 < nEnd1)
823 m_rData1.SetChanged( m_rMoved1.GetLineNum( nStt1++ ));
824
825 else
826 {
827 sal_uLong c, d, b;
828
829 /* Find a point of correspondence in the middle of the files. */
830
831 d = CheckDiag( nStt1, nEnd1, nStt2, nEnd2, &c );
832 b = m_pBDiag[ std::make_signed_t<decltype(d)>(d) ];
833
834 if( 1 != c )
835 {
836 /* Use that point to split this problem into two subproblems. */
837 Compare( nStt1, b, nStt2, b - d );
838 /* This used to use f instead of b,
839 but that is incorrect!
840 It is not necessarily the case that diagonal d
841 has a snake from b to f. */
842 Compare( b, nEnd1, b - d, nEnd2 );
843 }
844 }
845 }
846
847 sal_uLong Compare::CompareSequence::CheckDiag( sal_uLong nStt1, sal_uLong nEnd1,
848 sal_uLong nStt2, sal_uLong nEnd2, sal_uLong* pCost )
849 {
850 const tools::Long dmin = nStt1 - nEnd2; /* Minimum valid diagonal. */
851 const tools::Long dmax = nEnd1 - nStt2; /* Maximum valid diagonal. */
852 const tools::Long fmid = nStt1 - nStt2; /* Center diagonal of top-down search. */
853 const tools::Long bmid = nEnd1 - nEnd2; /* Center diagonal of bottom-up search. */
854
855 tools::Long fmin = fmid, fmax = fmid; /* Limits of top-down search. */
856 tools::Long bmin = bmid, bmax = bmid; /* Limits of bottom-up search. */
857
858 tools::Long c; /* Cost. */
859 tools::Long odd = (fmid - bmid) & 1; /* True if southeast corner is on an odd
860 diagonal with respect to the northwest. */
861
862 m_pFDiag[fmid] = nStt1;
863 m_pBDiag[bmid] = nEnd1;
864
865 for (c = 1;; ++c)
866 {
867 tools::Long d; /* Active diagonal. */
868
869 /* Extend the top-down search by an edit step in each diagonal. */
870 if (fmin > dmin)
871 m_pFDiag[--fmin - 1] = -1;
872 else
873 ++fmin;
874 if (fmax < dmax)
875 m_pFDiag[++fmax + 1] = -1;
876 else
877 --fmax;
878 for (d = fmax; d >= fmin; d -= 2)
879 {
880 tools::Long x, y, tlo = m_pFDiag[d - 1], thi = m_pFDiag[d + 1];
881
882 if (tlo >= thi)
883 x = tlo + 1;
884 else
885 x = thi;
886 y = x - d;
887 while( o3tl::make_unsigned(x) < nEnd1 && o3tl::make_unsigned(y) < nEnd2 &&
888 m_rMoved1.GetIndex( x ) == m_rMoved2.GetIndex( y ))
889 {
890 ++x;
891 ++y;
892 }
893 m_pFDiag[d] = x;
894 if( odd && bmin <= d && d <= bmax && m_pBDiag[d] <= m_pFDiag[d] )
895 {
896 *pCost = 2 * c - 1;
897 return d;
898 }
899 }
900
901 /* Similar extend the bottom-up search. */
902 if (bmin > dmin)
903 m_pBDiag[--bmin - 1] = INT_MAX;
904 else
905 ++bmin;
906 if (bmax < dmax)
907 m_pBDiag[++bmax + 1] = INT_MAX;
908 else
909 --bmax;
910 for (d = bmax; d >= bmin; d -= 2)
911 {
912 tools::Long x, y, tlo = m_pBDiag[d - 1], thi = m_pBDiag[d + 1];
913
914 if (tlo < thi)
915 x = tlo;
916 else
917 x = thi - 1;
918 y = x - d;
919 while( o3tl::make_unsigned(x) > nStt1 && o3tl::make_unsigned(y) > nStt2 &&
920 m_rMoved1.GetIndex( x - 1 ) == m_rMoved2.GetIndex( y - 1 ))
921 {
922 --x;
923 --y;
924 }
925 m_pBDiag[d] = x;
926 if (!odd && fmin <= d && d <= fmax && m_pBDiag[d] <= m_pFDiag[d])
927 {
928 *pCost = 2 * c;
929 return d;
930 }
931 }
932 }
933 }
934
935 namespace
936 {
937 void lcl_ShiftBoundariesOneway( CompareData* const pData, CompareData const * const pOtherData)
938 {
939 sal_uLong i = 0;
940 sal_uLong j = 0;
941 sal_uLong i_end = pData->GetLineCount();
942 sal_uLong preceding = ULONG_MAX;
943 sal_uLong other_preceding = ULONG_MAX;
944
945 while (true)
946 {
947 sal_uLong start, other_start;
948
949 /* Scan forwards to find beginning of another run of changes.
950 Also keep track of the corresponding point in the other file. */
951
952 while( i < i_end && !pData->GetChanged( i ) )
953 {
954 while( pOtherData->GetChanged( j++ ))
955 /* Non-corresponding lines in the other file
956 will count as the preceding batch of changes. */
957 other_preceding = j;
958 i++;
959 }
960
961 if (i == i_end)
962 break;
963
964 start = i;
965 other_start = j;
966
967 while (true)
968 {
969 /* Now find the end of this run of changes. */
970
971 while( pData->GetChanged( ++i ))
972 ;
973
974 /* If the first changed line matches the following unchanged one,
975 and this run does not follow right after a previous run,
976 and there are no lines deleted from the other file here,
977 then classify the first changed line as unchanged
978 and the following line as changed in its place. */
979
980 /* You might ask, how could this run follow right after another?
981 Only because the previous run was shifted here. */
982
983 if( i != i_end &&
984 pData->GetIndex( start ) == pData->GetIndex( i ) &&
985 !pOtherData->GetChanged( j ) &&
986 start != preceding && other_start != other_preceding )
987 {
988 pData->SetChanged( start++, false );
989 pData->SetChanged( i );
990 /* Since one line-that-matches is now before this run
991 instead of after, we must advance in the other file
992 to keep in sync. */
993 ++j;
994 }
995 else
996 break;
997 }
998
999 preceding = i;
1000 other_preceding = j;
1001 }
1002 }
1003 }
1004
1005 void Compare::ShiftBoundaries( CompareData& rData1, CompareData& rData2 )
1006 {
1007 lcl_ShiftBoundariesOneway(&rData1, &rData2);
1008 lcl_ShiftBoundariesOneway(&rData2, &rData1);
1009 }
1010
1011 sal_uLong SwCompareLine::GetHashValue() const
1012 {
1013 sal_uLong nRet = 0;
1014 switch( m_pNode->GetNodeType() )
1015 {
1016 case SwNodeType::Text:
1017 nRet = GetTextNodeHashValue( *m_pNode->GetTextNode(), nRet );
1018 break;
1019
1020 case SwNodeType::Table:
1021 {
1022 const SwNode* pEndNd = m_pNode->EndOfSectionNode();
1023 SwNodeIndex aIdx( *m_pNode );
1024 while( &aIdx.GetNode() != pEndNd )
1025 {
1026 if( aIdx.GetNode().IsTextNode() )
1027 nRet = GetTextNodeHashValue( *aIdx.GetNode().GetTextNode(), nRet );
1028 ++aIdx;
1029 }
1030 }
1031 break;
1032
1033 case SwNodeType::Section:
1034 {
1035 OUString sStr( GetText() );
1036 for( sal_Int32 n = 0; n < sStr.getLength(); ++n )
1037 nRet = (nRet << 1) + sStr[ n ];
1038 }
1039 break;
1040
1041 case SwNodeType::Grf:
1042 case SwNodeType::Ole:
1043 // Fixed ID? Should never occur ...
1044 break;
1045 default: break;
1046 }
1047 return nRet;
1048 }
1049
1050 const SwNode& SwCompareLine::GetEndNode() const
1051 {
1052 const SwNode* pNd = m_pNode;
1053 switch( m_pNode->GetNodeType() )
1054 {
1055 case SwNodeType::Table:
1056 pNd = m_pNode->EndOfSectionNode();
1057 break;
1058
1059 case SwNodeType::Section:
1060 {
1061 const SwSectionNode& rSNd = static_cast<const SwSectionNode&>(*m_pNode);
1062 const SwSection& rSect = rSNd.GetSection();
1063 if( SectionType::Content != rSect.GetType() || rSect.IsProtect() )
1064 pNd = m_pNode->EndOfSectionNode();
1065 }
1066 break;
1067 default: break;
1068 }
1069 return *pNd;
1070 }
1071
1072 bool SwCompareLine::Compare( const SwCompareLine& rLine ) const
1073 {
1074 return CompareNode( *m_pNode, *rLine.m_pNode );
1075 }
1076
1077 namespace
1078 {
1079 OUString SimpleTableToText(const SwNode &rNode)
1080 {
1081 OUStringBuffer sRet;
1082 const SwNode* pEndNd = rNode.EndOfSectionNode();
1083 SwNodeIndex aIdx( rNode );
1084 while (&aIdx.GetNode() != pEndNd)
1085 {
1086 if (aIdx.GetNode().IsTextNode())
1087 {
1088 if (sRet.getLength())
1089 {
1090 sRet.append( '\n' );
1091 }
1092 sRet.append( aIdx.GetNode().GetTextNode()->GetExpandText(nullptr) );
1093 }
1094 ++aIdx;
1095 }
1096 return sRet.makeStringAndClear();
1097 }
1098 }
1099
1100 bool SwCompareLine::CompareNode( const SwNode& rDstNd, const SwNode& rSrcNd )
1101 {
1102 if( rSrcNd.GetNodeType() != rDstNd.GetNodeType() )
1103 return false;
1104
1105 bool bRet = false;
1106
1107 switch( rDstNd.GetNodeType() )
1108 {
1109 case SwNodeType::Text:
1110 bRet = CompareTextNd( *rDstNd.GetTextNode(), *rSrcNd.GetTextNode() )
1111 && ( !CmpOptions.bUseRsid || rDstNd.GetTextNode()->CompareParRsid( *rSrcNd.GetTextNode() ) );
1112 break;
1113
1114 case SwNodeType::Table:
1115 {
1116 const SwTableNode& rTSrcNd = static_cast<const SwTableNode&>(rSrcNd);
1117 const SwTableNode& rTDstNd = static_cast<const SwTableNode&>(rDstNd);
1118
1119 bRet = ( rTSrcNd.EndOfSectionIndex() - rTSrcNd.GetIndex() ) ==
1120 ( rTDstNd.EndOfSectionIndex() - rTDstNd.GetIndex() );
1121
1122 // --> #i107826#: compare actual table content
1123 if (bRet)
1124 {
1125 bRet = (SimpleTableToText(rSrcNd) == SimpleTableToText(rDstNd));
1126 }
1127 }
1128 break;
1129
1130 case SwNodeType::Section:
1131 {
1132 const SwSectionNode& rSSrcNd = static_cast<const SwSectionNode&>(rSrcNd),
1133 & rSDstNd = static_cast<const SwSectionNode&>(rDstNd);
1134 const SwSection& rSrcSect = rSSrcNd.GetSection(),
1135 & rDstSect = rSDstNd.GetSection();
1136 SectionType eSrcSectType = rSrcSect.GetType(),
1137 eDstSectType = rDstSect.GetType();
1138 switch( eSrcSectType )
1139 {
1140 case SectionType::Content:
1141 bRet = SectionType::Content == eDstSectType &&
1142 rSrcSect.IsProtect() == rDstSect.IsProtect();
1143 if( bRet && rSrcSect.IsProtect() )
1144 {
1145 // the only have they both the same size
1146 bRet = ( rSSrcNd.EndOfSectionIndex() - rSSrcNd.GetIndex() ) ==
1147 ( rSDstNd.EndOfSectionIndex() - rSDstNd.GetIndex() );
1148 }
1149 break;
1150
1151 case SectionType::ToxHeader:
1152 case SectionType::ToxContent:
1153 if( SectionType::ToxHeader == eDstSectType ||
1154 SectionType::ToxContent == eDstSectType )
1155 {
1156 // the same type of TOX?
1157 const SwTOXBase* pSrcTOX = rSrcSect.GetTOXBase();
1158 const SwTOXBase* pDstTOX = rDstSect.GetTOXBase();
1159 bRet = pSrcTOX && pDstTOX
1160 && pSrcTOX->GetType() == pDstTOX->GetType()
1161 && pSrcTOX->GetTitle() == pDstTOX->GetTitle()
1162 && pSrcTOX->GetTypeName() == pDstTOX->GetTypeName()
1163 ;
1164 }
1165 break;
1166
1167 case SectionType::DdeLink:
1168 case SectionType::FileLink:
1169 bRet = eSrcSectType == eDstSectType &&
1170 rSrcSect.GetLinkFileName() ==
1171 rDstSect.GetLinkFileName();
1172 break;
1173 }
1174 }
1175 break;
1176
1177 case SwNodeType::End:
1178 bRet = rSrcNd.StartOfSectionNode()->GetNodeType() ==
1179 rDstNd.StartOfSectionNode()->GetNodeType();
1180
1181 // --> #i107826#: compare actual table content
1182 if (bRet && rSrcNd.StartOfSectionNode()->GetNodeType() == SwNodeType::Table)
1183 {
1184 bRet = CompareNode(
1185 *rSrcNd.StartOfSectionNode(), *rDstNd.StartOfSectionNode());
1186 }
1187
1188 break;
1189
1190 default: break;
1191 }
1192 return bRet;
1193 }
1194
1195 OUString SwCompareLine::GetText() const
1196 {
1197 OUString sRet;
1198 switch( m_pNode->GetNodeType() )
1199 {
1200 case SwNodeType::Text:
1201 sRet = m_pNode->GetTextNode()->GetExpandText(nullptr);
1202 break;
1203
1204 case SwNodeType::Table:
1205 {
1206 sRet = "Tabelle: " + SimpleTableToText(*m_pNode);
1207 }
1208 break;
1209
1210 case SwNodeType::Section:
1211 {
1212 sRet = "Section - Node:";
1213
1214 const SwSectionNode& rSNd = static_cast<const SwSectionNode&>(*m_pNode);
1215 const SwSection& rSect = rSNd.GetSection();
1216 switch( rSect.GetType() )
1217 {
1218 case SectionType::Content:
1219 if( rSect.IsProtect() )
1220 sRet += OUString::number(
1221 sal_Int32(rSNd.EndOfSectionIndex() - rSNd.GetIndex()) );
1222 break;
1223
1224 case SectionType::ToxHeader:
1225 case SectionType::ToxContent:
1226 {
1227 const SwTOXBase* pTOX = rSect.GetTOXBase();
1228 if( pTOX )
1229 sRet += pTOX->GetTitle() + pTOX->GetTypeName() +
1230 OUString::number(pTOX->GetType());
1231 }
1232 break;
1233
1234 case SectionType::DdeLink:
1235 case SectionType::FileLink:
1236 sRet += rSect.GetLinkFileName();
1237 break;
1238 }
1239 }
1240 break;
1241
1242 case SwNodeType::Grf:
1243 sRet = "Grafik - Node:";
1244 break;
1245 case SwNodeType::Ole:
1246 sRet = "OLE - Node:";
1247 break;
1248 default: break;
1249 }
1250 return sRet;
1251 }
1252
1253 sal_uLong SwCompareLine::GetTextNodeHashValue( const SwTextNode& rNd, sal_uLong nVal )
1254 {
1255 OUString sStr( rNd.GetExpandText(nullptr) );
1256 for( sal_Int32 n = 0; n < sStr.getLength(); ++n )
1257 nVal = (nVal << 1 ) + sStr[ n ];
1258 return nVal;
1259 }
1260
1261 bool SwCompareLine::CompareTextNd( const SwTextNode& rDstNd,
1262 const SwTextNode& rSrcNd )
1263 {
1264 bool bRet = false;
1265 // Very simple at first
1266 if( rDstNd.GetText() == rSrcNd.GetText() )
1267 {
1268 // The text is the same, but are the "special attributes" (0xFF) also the same?
1269 bRet = true;
1270 }
1271 return bRet;
1272 }
1273
1274 bool SwCompareLine::ChangesInLine( const SwCompareLine& rLine,
1275 std::unique_ptr<SwPaM>& rpInsRing, std::unique_ptr<SwPaM>& rpDelRing ) const
1276 {
1277 bool bRet = false;
1278
1279 // Only compare textnodes
1280 if( SwNodeType::Text == m_pNode->GetNodeType() &&
1281 SwNodeType::Text == rLine.GetNode().GetNodeType() )
1282 {
1283 SwTextNode& rDstNd = *const_cast<SwTextNode*>(m_pNode->GetTextNode());
1284 const SwTextNode& rSrcNd = *rLine.GetNode().GetTextNode();
1285 SwDoc& rDstDoc = rDstNd.GetDoc();
1286
1287 int nLcsLen = 0;
1288
1289 int nDstLen = rDstNd.GetText().getLength();
1290 int nSrcLen = rSrcNd.GetText().getLength();
1291
1292 int nMinLen = std::min( nDstLen , nSrcLen );
1293 int nAvgLen = ( nDstLen + nSrcLen )/2;
1294
1295 std::vector<int> aLcsDst( nMinLen + 1 );
1296 std::vector<int> aLcsSrc( nMinLen + 1 );
1297
1298 if( CmpOptions.eCmpMode == SwCompareMode::ByWord )
1299 {
1300 std::vector<int> aTmpLcsDst( nMinLen + 1 );
1301 std::vector<int> aTmpLcsSrc( nMinLen + 1 );
1302
1303 WordArrayComparator aCmp( &rDstNd, &rSrcNd );
1304
1305 LgstCommonSubseq aSeq( aCmp );
1306
1307 nLcsLen = aSeq.Find( aTmpLcsDst.data(), aTmpLcsSrc.data() );
1308
1309 if( CmpOptions.nIgnoreLen )
1310 {
1311 nLcsLen = CommonSubseq::IgnoreIsolatedPieces( aTmpLcsDst.data(), aTmpLcsSrc.data(),
1312 aCmp.GetLen1(), aCmp.GetLen2(),
1313 nLcsLen, CmpOptions.nIgnoreLen );
1314 }
1315
1316 nLcsLen = aCmp.GetCharSequence( aTmpLcsDst.data(), aTmpLcsSrc.data(),
1317 aLcsDst.data(), aLcsSrc.data(), nLcsLen );
1318 }
1319 else
1320 {
1321 CharArrayComparator aCmp( &rDstNd, &rSrcNd );
1322 LgstCommonSubseq aSeq( aCmp );
1323
1324 nLcsLen = aSeq.Find( aLcsDst.data(), aLcsSrc.data() );
1325
1326 if( CmpOptions.nIgnoreLen )
1327 {
1328 nLcsLen = CommonSubseq::IgnoreIsolatedPieces( aLcsDst.data(), aLcsSrc.data(), nDstLen,
1329 nSrcLen, nLcsLen,
1330 CmpOptions.nIgnoreLen );
1331 }
1332 }
1333
1334 // find the sum of the squares of the continuous substrings
1335 int nSqSum = 0;
1336 int nCnt = 1;
1337 for( int i = 0; i < nLcsLen; i++ )
1338 {
1339 if( i != nLcsLen - 1 && aLcsDst[i] + 1 == aLcsDst[i + 1]
1340 && aLcsSrc[i] + 1 == aLcsSrc[i + 1] )
1341 {
1342 nCnt++;
1343 }
1344 else
1345 {
1346 nSqSum += nCnt*nCnt;
1347 nCnt = 1;
1348 }
1349 }
1350
1351 // Don't compare if there aren't enough similarities
1352 if ( nAvgLen >= 8 && nSqSum*32 < nAvgLen*nAvgLen )
1353 {
1354 return false;
1355 }
1356
1357 // Show the differences
1358 int nSkip = 0;
1359 for( int i = 0; i <= nLcsLen; i++ )
1360 {
1361 int nDstFrom = i ? (aLcsDst[i - 1] + 1) : 0;
1362 int nDstTo = ( i == nLcsLen ) ? nDstLen : aLcsDst[i];
1363 int nSrcFrom = i ? (aLcsSrc[i - 1] + 1) : 0;
1364 int nSrcTo = ( i == nLcsLen ) ? nSrcLen : aLcsSrc[i];
1365
1366 SwPaM aPam( rDstNd, nDstTo + nSkip );
1367
1368 if ( nDstFrom < nDstTo )
1369 {
1370 SwPaM* pTmp = new SwPaM( *aPam.GetPoint(), rpInsRing.get() );
1371 if( !rpInsRing )
1372 rpInsRing.reset(pTmp);
1373 pTmp->SetMark();
1374 pTmp->GetMark()->SetContent(nDstFrom + nSkip);
1375 }
1376
1377 if ( nSrcFrom < nSrcTo )
1378 {
1379 bool bUndo = rDstDoc.GetIDocumentUndoRedo().DoesUndo();
1380 rDstDoc.GetIDocumentUndoRedo().DoUndo( false );
1381 SwPaM aCpyPam( rSrcNd, nSrcFrom );
1382 aCpyPam.SetMark();
1383 aCpyPam.GetPoint()->SetContent(nSrcTo);
1384 aCpyPam.GetDoc().getIDocumentContentOperations().CopyRange( aCpyPam, *aPam.GetPoint(),
1385 SwCopyFlags::CheckPosInFly);
1386 rDstDoc.GetIDocumentUndoRedo().DoUndo( bUndo );
1387
1388 SwPaM* pTmp = new SwPaM( *aPam.GetPoint(), rpDelRing.get() );
1389 if( !rpDelRing )
1390 rpDelRing.reset(pTmp);
1391
1392 pTmp->SetMark();
1393 pTmp->GetMark()->SetContent(nDstTo + nSkip);
1394 nSkip += nSrcTo - nSrcFrom;
1395
1396 if( rpInsRing )
1397 {
1398 SwPaM* pCorr = rpInsRing->GetPrev();
1399 if( *pCorr->GetPoint() == *pTmp->GetPoint() )
1400 *pCorr->GetPoint() = *pTmp->GetMark();
1401 }
1402 }
1403 }
1404
1405 bRet = true;
1406 }
1407
1408 return bRet;
1409 }
1410
1411 SwNodeOffset CompareData::NextIdx( const SwNode* pNd )
1412 {
1413 if( pNd->IsStartNode() )
1414 {
1415 if( pNd->IsTableNode() )
1416 pNd = pNd->EndOfSectionNode();
1417 else
1418 {
1419 const SwSectionNode* pSNd = pNd->GetSectionNode();
1420 if( pSNd &&
1421 ( SectionType::Content != pSNd->GetSection().GetType() ||
1422 pSNd->GetSection().IsProtect() ) )
1423 pNd = pNd->EndOfSectionNode();
1424 }
1425 }
1426 return pNd->GetIndex() + 1;
1427 }
1428
1429 SwNodeOffset CompareData::PrevIdx( const SwNode* pNd )
1430 {
1431 if( pNd->IsEndNode() )
1432 {
1433 if( pNd->StartOfSectionNode()->IsTableNode() )
1434 pNd = pNd->StartOfSectionNode();
1435 else
1436 {
1437 const SwSectionNode* pSNd = pNd->StartOfSectionNode()->GetSectionNode();
1438 if( pSNd &&
1439 ( SectionType::Content != pSNd->GetSection().GetType() ||
1440 pSNd->GetSection().IsProtect() ) )
1441 pNd = pNd->StartOfSectionNode();
1442 }
1443 }
1444 return pNd->GetIndex() - 1;
1445 }
1446
1447 void CompareData::CheckRanges( CompareData& rData )
1448 {
1449 const SwNodes& rSrcNds = rData.m_rDoc.GetNodes();
1450 const SwNodes& rDstNds = m_rDoc.GetNodes();
1451
1452 const SwNode& rSrcEndNd = rData.GetEndOfContent();
1453 const SwNode& rDstEndNd = GetEndOfContent();
1454
1455 SwNodeOffset nSrcSttIdx = NextIdx( rSrcEndNd.StartOfSectionNode() );
1456 SwNodeOffset nSrcEndIdx = rSrcEndNd.GetIndex();
1457
1458 SwNodeOffset nDstSttIdx = NextIdx( rDstEndNd.StartOfSectionNode() );
1459 SwNodeOffset nDstEndIdx = rDstEndNd.GetIndex();
1460
1461 while( nSrcSttIdx < nSrcEndIdx && nDstSttIdx < nDstEndIdx )
1462 {
1463 const SwNode* pSrcNd = rSrcNds[ nSrcSttIdx ];
1464 const SwNode* pDstNd = rDstNds[ nDstSttIdx ];
1465 if( !SwCompareLine::CompareNode( *pSrcNd, *pDstNd ))
1466 break;
1467
1468 nSrcSttIdx = NextIdx( pSrcNd );
1469 nDstSttIdx = NextIdx( pDstNd );
1470 }
1471
1472 nSrcEndIdx = PrevIdx( &rSrcEndNd );
1473 nDstEndIdx = PrevIdx( &rDstEndNd );
1474 while( nSrcSttIdx < nSrcEndIdx && nDstSttIdx < nDstEndIdx )
1475 {
1476 const SwNode* pSrcNd = rSrcNds[ nSrcEndIdx ];
1477 const SwNode* pDstNd = rDstNds[ nDstEndIdx ];
1478 if( !SwCompareLine::CompareNode( *pSrcNd, *pDstNd ))
1479 break;
1480
1481 nSrcEndIdx = PrevIdx( pSrcNd );
1482 nDstEndIdx = PrevIdx( pDstNd );
1483 }
1484
1485 while( nSrcSttIdx <= nSrcEndIdx )
1486 {
1487 const SwNode* pNd = rSrcNds[ nSrcSttIdx ];
1488 rData.InsertLine( SwCompareLine( *pNd ) );
1489 nSrcSttIdx = NextIdx( pNd );
1490 }
1491
1492 while( nDstSttIdx <= nDstEndIdx )
1493 {
1494 const SwNode* pNd = rDstNds[ nDstSttIdx ];
1495 InsertLine( SwCompareLine( *pNd ) );
1496 nDstSttIdx = NextIdx( pNd );
1497 }
1498 }
1499
1500 void CompareData::ShowInsert( sal_uLong nStt, sal_uLong nEnd )
1501 {
1502 SwPaM* pTmp = new SwPaM( GetLine( nStt ).GetNode(), 0,
1503 GetLine( nEnd-1 ).GetEndNode(), 0,
1504 m_pInsertRing.get() );
1505 if( !m_pInsertRing )
1506 m_pInsertRing.reset( pTmp );
1507
1508 // #i65201#: These SwPaMs are calculated smaller than needed, see comment below
1509 }
1510
1511 void CompareData::ShowDelete(
1512 const CompareData& rData,
1513 sal_uLong nStt,
1514 sal_uLong nEnd,
1515 sal_uLong nInsPos )
1516 {
1517 SwNodeRange aRg(
1518 rData.GetLine( nStt ).GetNode(), SwNodeOffset(0),
1519 rData.GetLine( nEnd-1 ).GetEndNode(), SwNodeOffset(1) );
1520
1521 SwNodeOffset nOffset(0);
1522 std::optional<SwCompareLine> xLine;
1523 if( nInsPos >= 1 )
1524 {
1525 if( GetLineCount() == nInsPos )
1526 {
1527 xLine = GetLine( nInsPos-1 );
1528 nOffset = SwNodeOffset(1);
1529 }
1530 else
1531 xLine = GetLine( nInsPos );
1532 }
1533
1534 const SwNode* pLineNd;
1535 if( xLine )
1536 {
1537 if( nOffset )
1538 pLineNd = &xLine->GetEndNode();
1539 else
1540 pLineNd = &xLine->GetNode();
1541 }
1542 else
1543 {
1544 pLineNd = &GetEndOfContent();
1545 nOffset = SwNodeOffset(0);
1546 }
1547
1548 SwNodeIndex aInsPos( *pLineNd, nOffset );
1549 SwNodeIndex aSavePos( aInsPos, -1 );
1550
1551 rData.m_rDoc.GetDocumentContentOperationsManager().CopyWithFlyInFly(aRg, aInsPos.GetNode());
1552 m_rDoc.getIDocumentState().SetModified();
1553 ++aSavePos;
1554
1555 // #i65201#: These SwPaMs are calculated when the (old) delete-redlines are hidden,
1556 // they will be inserted when the delete-redlines are shown again.
1557 // To avoid unwanted insertions of delete-redlines into these new redlines, what happens
1558 // especially at the end of the document, I reduce the SwPaM by one node.
1559 // Before the new redlines are inserted, they have to expand again.
1560 SwPaM* pTmp = new SwPaM( aSavePos.GetNode(), aInsPos.GetNode(), SwNodeOffset(0), SwNodeOffset(-1), m_pDelRing.get() );
1561 if( !m_pDelRing )
1562 m_pDelRing.reset(pTmp);
1563
1564 if( m_pInsertRing )
1565 {
1566 SwPaM* pCorr = m_pInsertRing->GetPrev();
1567 if( *pCorr->GetPoint() == *pTmp->GetPoint() )
1568 {
1569 SwNodeIndex aTmpPos( pTmp->GetMark()->GetNode(), -1 );
1570 pCorr->GetPoint()->Assign( aTmpPos );
1571 }
1572 }
1573 }
1574
1575 void CompareData::CheckForChangesInLine( const CompareData& rData,
1576 sal_uLong nStt, sal_uLong nEnd,
1577 sal_uLong nThisStt, sal_uLong nThisEnd )
1578 {
1579 LineArrayComparator aCmp( *this, rData, nThisStt, nThisEnd,
1580 nStt, nEnd );
1581
1582 int nMinLen = std::min( aCmp.GetLen1(), aCmp.GetLen2() );
1583 std::unique_ptr<int[]> pLcsDst(new int[ nMinLen ]);
1584 std::unique_ptr<int[]> pLcsSrc(new int[ nMinLen ]);
1585
1586 FastCommonSubseq subseq( aCmp );
1587 int nLcsLen = subseq.Find( pLcsDst.get(), pLcsSrc.get() );
1588 for (int i = 0; i <= nLcsLen; i++)
1589 {
1590 // Beginning of inserted lines (inclusive)
1591 int nDstFrom = i ? pLcsDst[i - 1] + 1 : 0;
1592 // End of inserted lines (exclusive)
1593 int nDstTo = ( i == nLcsLen ) ? aCmp.GetLen1() : pLcsDst[i];
1594 // Beginning of deleted lines (inclusive)
1595 int nSrcFrom = i ? pLcsSrc[i - 1] + 1 : 0;
1596 // End of deleted lines (exclusive)
1597 int nSrcTo = ( i == nLcsLen ) ? aCmp.GetLen2() : pLcsSrc[i];
1598
1599 if( i )
1600 {
1601 const SwCompareLine aDstLn = GetLine( nThisStt + nDstFrom - 1 );
1602 const SwCompareLine aSrcLn = rData.GetLine( nStt + nSrcFrom - 1 );
1603
1604 // Show differences in detail for lines that
1605 // were matched as only slightly different
1606 if( !aDstLn.ChangesInLine( aSrcLn, m_pInsertRing, m_pDelRing ) )
1607 {
1608 ShowInsert( nThisStt + nDstFrom - 1, nThisStt + nDstFrom );
1609 ShowDelete( rData, nStt + nSrcFrom - 1, nStt + nSrcFrom,
1610 nThisStt + nDstFrom );
1611 }
1612 }
1613
1614 // Lines missing from source are inserted
1615 if( nDstFrom != nDstTo )
1616 {
1617 ShowInsert( nThisStt + nDstFrom, nThisStt + nDstTo );
1618 }
1619
1620 // Lines missing from destination are deleted
1621 if( nSrcFrom != nSrcTo )
1622 {
1623 ShowDelete( rData, nStt + nSrcFrom, nStt + nSrcTo, nThisStt + nDstTo );
1624 }
1625 }
1626 }
1627
1628 void CompareData::SetRedlinesToDoc( bool bUseDocInfo )
1629 {
1630 SwPaM* pTmp = m_pDelRing.get();
1631
1632 // get the Author / TimeStamp from the "other" document info
1633 std::size_t nAuthor = m_rDoc.getIDocumentRedlineAccess().GetRedlineAuthor();
1634 DateTime aTimeStamp( DateTime::SYSTEM );
1635 SwDocShell *pDocShell(m_rDoc.GetDocShell());
1636 OSL_ENSURE(pDocShell, "no SwDocShell");
1637 if (pDocShell) {
1638 uno::Reference<document::XDocumentPropertiesSupplier> xDPS(
1639 pDocShell->GetModel(), uno::UNO_QUERY_THROW);
1640 uno::Reference<document::XDocumentProperties> xDocProps(
1641 xDPS->getDocumentProperties());
1642 OSL_ENSURE(xDocProps.is(), "Doc has no DocumentProperties");
1643
1644 if( bUseDocInfo && xDocProps.is() ) {
1645 OUString aTmp( 1 == xDocProps->getEditingCycles()
1646 ? xDocProps->getAuthor()
1647 : xDocProps->getModifiedBy() );
1648 util::DateTime uDT( 1 == xDocProps->getEditingCycles()
1649 ? xDocProps->getCreationDate()
1650 : xDocProps->getModificationDate() );
1651
1652 if( !aTmp.isEmpty() )
1653 {
1654 nAuthor = m_rDoc.getIDocumentRedlineAccess().InsertRedlineAuthor( aTmp );
1655 aTimeStamp = DateTime(uDT);
1656 }
1657 }
1658 }
1659
1660 if( pTmp )
1661 {
1662 SwRedlineData aRedlnData( RedlineType::Delete, nAuthor, aTimeStamp,
1663 OUString(), nullptr );
1664 do {
1665 // #i65201#: Expand again, see comment above.
1666 if( pTmp->GetPoint()->GetContentIndex() == 0 )
1667 {
1668 pTmp->GetPoint()->Adjust(SwNodeOffset(1));
1669 }
1670 // #i101009#
1671 // prevent redlines that end on structural end node
1672 if (& GetEndOfContent() ==
1673 & pTmp->GetPoint()->GetNode())
1674 {
1675 pTmp->GetPoint()->Adjust(SwNodeOffset(-1));
1676 SwContentNode *const pContentNode( pTmp->GetPointContentNode() );
1677 if( pContentNode )
1678 pTmp->GetPoint()->SetContent( pContentNode->Len() );
1679 // tdf#106218 try to avoid losing a paragraph break here:
1680 if (pTmp->GetMark()->GetContentIndex() == 0)
1681 {
1682 SwNodeIndex const prev(pTmp->GetMark()->GetNode(), -1);
1683 if (prev.GetNode().IsTextNode())
1684 {
1685 pTmp->GetMark()->Assign(
1686 *prev.GetNode().GetTextNode(),
1687 prev.GetNode().GetTextNode()->Len());
1688 }
1689 }
1690 }
1691
1692 m_rDoc.getIDocumentRedlineAccess().DeleteRedline( *pTmp, false, RedlineType::Any );
1693
1694 if (m_rDoc.GetIDocumentUndoRedo().DoesUndo())
1695 {
1696 m_rDoc.GetIDocumentUndoRedo().AppendUndo(
1697 std::make_unique<SwUndoCompDoc>( *pTmp, false ));
1698 }
1699 m_rDoc.getIDocumentRedlineAccess().AppendRedline( new SwRangeRedline( aRedlnData, *pTmp ), true );
1700
1701 } while( m_pDelRing.get() != ( pTmp = pTmp->GetNext()) );
1702 }
1703
1704 pTmp = m_pInsertRing.get();
1705 if( !pTmp )
1706 return;
1707
1708 do {
1709 if( pTmp->GetPoint()->GetContentIndex() == 0 )
1710 {
1711 pTmp->GetPoint()->Adjust(SwNodeOffset(1));
1712 }
1713 // #i101009#
1714 // prevent redlines that end on structural end node
1715 if (& GetEndOfContent() ==
1716 & pTmp->GetPoint()->GetNode())
1717 {
1718 pTmp->GetPoint()->Adjust(SwNodeOffset(-1));
1719 SwContentNode *const pContentNode( pTmp->GetPointContentNode() );
1720 if( pContentNode )
1721 pTmp->GetPoint()->SetContent( pContentNode->Len() );
1722 // tdf#106218 try to avoid losing a paragraph break here:
1723 if (pTmp->GetMark()->GetContentIndex() == 0)
1724 {
1725 SwNodeIndex const prev(pTmp->GetMark()->GetNode(), -1);
1726 if (prev.GetNode().IsTextNode())
1727 {
1728 pTmp->GetMark()->Assign(
1729 *prev.GetNode().GetTextNode(),
1730 prev.GetNode().GetTextNode()->Len());
1731 }
1732 }
1733 }
1734 } while( m_pInsertRing.get() != ( pTmp = pTmp->GetNext()) );
1735 SwRedlineData aRedlnData( RedlineType::Insert, nAuthor, aTimeStamp,
1736 OUString(), nullptr );
1737
1738 // combine consecutive
1739 if( pTmp->GetNext() != m_pInsertRing.get() )
1740 {
1741 do {
1742 // coverity[deref_arg] - the SwPaM delete moves a new entry into GetNext()
1743 SwPosition& rSttEnd = *pTmp->End(),
1744 & rEndStt = *pTmp->GetNext()->Start();
1745 const SwContentNode* pCNd;
1746 if( rSttEnd == rEndStt ||
1747 (!rEndStt.GetContentIndex() &&
1748 rEndStt.GetNodeIndex() - 1 == rSttEnd.GetNodeIndex() &&
1749 nullptr != ( pCNd = rSttEnd.GetNode().GetContentNode() ) &&
1750 rSttEnd.GetContentIndex() == pCNd->Len()))
1751 {
1752 if( pTmp->GetNext() == m_pInsertRing.get() )
1753 {
1754 // are consecutive, so combine
1755 rEndStt = *pTmp->Start();
1756 delete pTmp;
1757 pTmp = m_pInsertRing.get();
1758 }
1759 else
1760 {
1761 // are consecutive, so combine
1762 rSttEnd = *pTmp->GetNext()->End();
1763 delete pTmp->GetNext();
1764 }
1765 }
1766 else
1767 pTmp = pTmp->GetNext();
1768 } while( m_pInsertRing.get() != pTmp );
1769 }
1770
1771 do {
1772 // coverity[deref_arg] - pTmp is valid here
1773 if (IDocumentRedlineAccess::AppendResult::APPENDED ==
1774 m_rDoc.getIDocumentRedlineAccess().AppendRedline(
1775 new SwRangeRedline(aRedlnData, *pTmp), true) &&
1776 m_rDoc.GetIDocumentUndoRedo().DoesUndo())
1777 {
1778 m_rDoc.GetIDocumentUndoRedo().AppendUndo(
1779 std::make_unique<SwUndoCompDoc>( *pTmp, true ));
1780 }
1781 } while( m_pInsertRing.get() != ( pTmp = pTmp->GetNext()) );
1782 }
1783
1784 typedef std::shared_ptr<CompareData> CompareDataPtr;
1785 typedef std::pair<CompareDataPtr, CompareDataPtr> CompareDataPtrPair;
1786 typedef std::vector<CompareDataPtrPair> Comparators;
1787
1788 namespace
1789 {
1790 Comparators buildComparators(SwDoc &rSrcDoc, SwDoc &rDestDoc)
1791 {
1792 Comparators aComparisons;
1793 //compare main text
1794 aComparisons.emplace_back(std::make_shared<CompareMainText>(rSrcDoc, true),
1795 std::make_shared<CompareMainText>(rDestDoc, true));
1796
1797 //if we have the same number of frames then try to compare within them
1798 const sw::SpzFrameFormats* pSrcFrameFormats = rSrcDoc.GetSpzFrameFormats();
1799 const sw::SpzFrameFormats* pDestFrameFormats = rDestDoc.GetSpzFrameFormats();
1800 if (pSrcFrameFormats->size() == pDestFrameFormats->size())
1801 {
1802 for(sw::FrameFormats<sw::SpzFrameFormat*>::size_type i = 0; i < pSrcFrameFormats->size(); ++i)
1803 {
1804 const sw::SpzFrameFormat& rSrcFormat = *(*pSrcFrameFormats)[i];
1805 const sw::SpzFrameFormat& rDestFormat = *(*pDestFrameFormats)[i];
1806 const SwNodeIndex* pSrcIdx = rSrcFormat.GetContent().GetContentIdx();
1807 const SwNodeIndex* pDestIdx = rDestFormat.GetContent().GetContentIdx();
1808 if (!pSrcIdx && !pDestIdx)
1809 continue;
1810 if (!pSrcIdx || !pDestIdx)
1811 break;
1812 const SwNode* pSrcNode = pSrcIdx->GetNode().EndOfSectionNode();
1813 const SwNode* pDestNode = pDestIdx->GetNode().EndOfSectionNode();
1814 if (!pSrcNode && !pDestNode)
1815 continue;
1816 if (!pSrcNode || !pDestNode)
1817 break;
1818 if (pSrcIdx->GetNodes()[pSrcIdx->GetIndex() + 1]->IsNoTextNode()
1819 || pDestIdx->GetNodes()[pDestIdx->GetIndex() + 1]->IsNoTextNode())
1820 {
1821 continue; // tdf#125660 don't redline GrfNode/OLENode
1822 }
1823 aComparisons.emplace_back(std::make_shared<CompareFrameFormatText>(rSrcDoc, *pSrcIdx),
1824 std::make_shared<CompareFrameFormatText>(rDestDoc, *pDestIdx));
1825 }
1826 }
1827 return aComparisons;
1828 }
1829 }
1830
1831 // Returns (the difference count?) if something is different
1832 tools::Long SwDoc::CompareDoc( const SwDoc& rDoc )
1833 {
1834 if( &rDoc == this )
1835 return 0;
1836
1837 tools::Long nRet = 0;
1838
1839 // Get comparison options
1840 CmpOptions.eCmpMode = SW_MOD()->GetCompareMode();
1841 if( CmpOptions.eCmpMode == SwCompareMode::Auto )
1842 {
1843 if( getRsidRoot() == rDoc.getRsidRoot() )
1844 {
1845 CmpOptions.eCmpMode = SwCompareMode::ByChar;
1846 CmpOptions.bUseRsid = true;
1847 CmpOptions.nIgnoreLen = 2;
1848 }
1849 else
1850 {
1851 CmpOptions.eCmpMode = SwCompareMode::ByWord;
1852 CmpOptions.bUseRsid = false;
1853 CmpOptions.nIgnoreLen = 3;
1854 }
1855 }
1856 else
1857 {
1858 CmpOptions.bUseRsid = getRsidRoot() == rDoc.getRsidRoot() && SW_MOD()->IsUseRsid();
1859 CmpOptions.nIgnoreLen = SW_MOD()->IsIgnorePieces() ? SW_MOD()->GetPieceLen() : 0;
1860 }
1861
1862 GetIDocumentUndoRedo().StartUndo(SwUndoId::EMPTY, nullptr);
1863 bool bDocWasModified = getIDocumentState().IsModified();
1864 SwDoc& rSrcDoc = const_cast<SwDoc&>(rDoc);
1865 bool bSrcModified = rSrcDoc.getIDocumentState().IsModified();
1866
1867 RedlineFlags eSrcRedlMode = rSrcDoc.getIDocumentRedlineAccess().GetRedlineFlags();
1868 rSrcDoc.getIDocumentRedlineAccess().SetRedlineFlags( RedlineFlags::ShowInsert );
1869 getIDocumentRedlineAccess().SetRedlineFlags(RedlineFlags::On | RedlineFlags::ShowInsert);
1870
1871 Comparators aComparisons(buildComparators(rSrcDoc, *this));
1872
1873 for (auto& a : aComparisons)
1874 {
1875 CompareData& rD0 = *a.first;
1876 CompareData& rD1 = *a.second;
1877 rD1.CompareLines( rD0 );
1878 nRet |= rD1.ShowDiffs( rD0 );
1879 }
1880
1881 if( nRet )
1882 {
1883 getIDocumentRedlineAccess().SetRedlineFlags(RedlineFlags::On |
1884 RedlineFlags::ShowInsert | RedlineFlags::ShowDelete);
1885
1886 for (auto& a : aComparisons)
1887 {
1888 CompareData& rD1 = *a.second;
1889 rD1.SetRedlinesToDoc( !bDocWasModified );
1890 }
1891 getIDocumentState().SetModified();
1892 }
1893
1894 rSrcDoc.getIDocumentRedlineAccess().SetRedlineFlags( eSrcRedlMode );
1895 getIDocumentRedlineAccess().SetRedlineFlags(RedlineFlags::ShowInsert | RedlineFlags::ShowDelete);
1896
1897 if( !bSrcModified )
1898 rSrcDoc.getIDocumentState().ResetModified();
1899
1900 GetIDocumentUndoRedo().EndUndo(SwUndoId::EMPTY, nullptr);
1901
1902 return nRet;
1903 }
1904
1905 namespace
1906 {
1907 struct SaveMergeRedline
1908 {
1909 const SwRangeRedline* pSrcRedl;
1910 SwRangeRedline* pDestRedl;
1911 SaveMergeRedline( const SwNode& rDstNd, const SwRangeRedline& rSrcRedl);
1912 sal_uInt16 InsertRedline(SwPaM* pLastDestRedline);
1913 };
1914 }
1915
1916 SaveMergeRedline::SaveMergeRedline( const SwNode& rDstNd,
1917 const SwRangeRedline& rSrcRedl)
1918 : pSrcRedl( &rSrcRedl )
1919 {
1920 SwPosition aPos( rDstNd );
1921
1922 const SwPosition* pStt = rSrcRedl.Start();
1923 if( rDstNd.IsContentNode() )
1924 aPos.SetContent( pStt->GetContentIndex() );
1925 pDestRedl = new SwRangeRedline( rSrcRedl.GetRedlineData(), aPos );
1926
1927 if( RedlineType::Delete != pDestRedl->GetType() )
1928 return;
1929
1930 // mark the area as deleted
1931 const SwPosition* pEnd = rSrcRedl.End();
1932
1933 pDestRedl->SetMark();
1934 pDestRedl->GetPoint()->Adjust( pEnd->GetNodeIndex() -
1935 pStt->GetNodeIndex() );
1936 if( pDestRedl->GetPointContentNode() )
1937 pDestRedl->GetPoint()->SetContent( pEnd->GetContentIndex() );
1938 }
1939
1940 sal_uInt16 SaveMergeRedline::InsertRedline(SwPaM* pLastDestRedline)
1941 {
1942 sal_uInt16 nIns = 0;
1943 SwDoc& rDoc = pDestRedl->GetDoc();
1944
1945 if( RedlineType::Insert == pDestRedl->GetType() )
1946 {
1947 // the part was inserted so copy it from the SourceDoc
1948 ::sw::UndoGuard const undoGuard(rDoc.GetIDocumentUndoRedo());
1949
1950 SwNodeIndex aSaveNd( pDestRedl->GetPoint()->GetNode(), -1 );
1951 const sal_Int32 nSaveCnt = pDestRedl->GetPoint()->GetContentIndex();
1952
1953 RedlineFlags eOld = rDoc.getIDocumentRedlineAccess().GetRedlineFlags();
1954 rDoc.getIDocumentRedlineAccess().SetRedlineFlags_intern(eOld | RedlineFlags::Ignore);
1955
1956 pSrcRedl->GetDoc().getIDocumentContentOperations().CopyRange(
1957 *const_cast<SwPaM*>(static_cast<const SwPaM*>(pSrcRedl)),
1958 *pDestRedl->GetPoint(), SwCopyFlags::CheckPosInFly);
1959
1960 rDoc.getIDocumentRedlineAccess().SetRedlineFlags_intern( eOld );
1961
1962 pDestRedl->SetMark();
1963 ++aSaveNd;
1964 pDestRedl->GetMark()->Assign( aSaveNd, nSaveCnt );
1965
1966 if( pLastDestRedline && *pLastDestRedline->GetPoint() == *pDestRedl->GetPoint() )
1967 *pLastDestRedline->GetPoint() = *pDestRedl->GetMark();
1968 }
1969 else
1970 {
1971 //JP 21.09.98: Bug 55909
1972 // If there already is a deleted or inserted one at the same position, we have to split it!
1973 SwPosition* pDStt = pDestRedl->GetMark(),
1974 * pDEnd = pDestRedl->GetPoint();
1975 SwRedlineTable::size_type n = 0;
1976
1977 // find the first redline for StartPos
1978 if( !rDoc.getIDocumentRedlineAccess().GetRedline( *pDStt, &n ) && n )
1979 --n;
1980
1981 const SwRedlineTable& rRedlineTable = rDoc.getIDocumentRedlineAccess().GetRedlineTable();
1982 for( ; n < rRedlineTable.size(); ++n )
1983 {
1984 SwRangeRedline* pRedl = rRedlineTable[ n ];
1985 SwPosition* pRStt = pRedl->Start(),
1986 * pREnd = pRedl->End();
1987 if( RedlineType::Delete == pRedl->GetType() ||
1988 RedlineType::Insert == pRedl->GetType() )
1989 {
1990 SwComparePosition eCmpPos = ComparePosition( *pDStt, *pDEnd, *pRStt, *pREnd );
1991 switch( eCmpPos )
1992 {
1993 case SwComparePosition::CollideStart:
1994 case SwComparePosition::Behind:
1995 break;
1996
1997 case SwComparePosition::Inside:
1998 case SwComparePosition::Equal:
1999 delete pDestRedl;
2000 pDestRedl = nullptr;
2001 [[fallthrough]];
2002
2003 case SwComparePosition::CollideEnd:
2004 case SwComparePosition::Before:
2005 n = rRedlineTable.size();
2006 break;
2007
2008 case SwComparePosition::Outside:
2009 assert(pDestRedl && "is this actually impossible");
2010 if (pDestRedl)
2011 {
2012 SwRangeRedline* pCpyRedl = new SwRangeRedline(
2013 pDestRedl->GetRedlineData(), *pDStt );
2014 pCpyRedl->SetMark();
2015 *pCpyRedl->GetPoint() = *pRStt;
2016
2017 std::unique_ptr<SwUndoCompDoc> pUndo;
2018 if (rDoc.GetIDocumentUndoRedo().DoesUndo())
2019 pUndo.reset(new SwUndoCompDoc( *pCpyRedl ));
2020
2021 // now modify doc: append redline, undo (and count)
2022 rDoc.getIDocumentRedlineAccess().AppendRedline( pCpyRedl, true );
2023 if( pUndo )
2024 {
2025 rDoc.GetIDocumentUndoRedo().AppendUndo(std::move(pUndo));
2026 }
2027 ++nIns;
2028
2029 *pDStt = *pREnd;
2030
2031 // we should start over now
2032 n = SwRedlineTable::npos;
2033 }
2034 break;
2035
2036 case SwComparePosition::OverlapBefore:
2037 *pDEnd = *pRStt;
2038 break;
2039
2040 case SwComparePosition::OverlapBehind:
2041 *pDStt = *pREnd;
2042 break;
2043 }
2044 }
2045 else if( *pDEnd <= *pRStt )
2046 break;
2047 }
2048
2049 }
2050
2051 if( pDestRedl )
2052 {
2053 std::unique_ptr<SwUndoCompDoc> pUndo;
2054 if (rDoc.GetIDocumentUndoRedo().DoesUndo())
2055 pUndo.reset(new SwUndoCompDoc( *pDestRedl ));
2056
2057 // now modify doc: append redline, undo (and count)
2058 IDocumentRedlineAccess::AppendResult const result(
2059 rDoc.getIDocumentRedlineAccess().AppendRedline(pDestRedl, true));
2060 if( pUndo )
2061 {
2062 rDoc.GetIDocumentUndoRedo().AppendUndo( std::move(pUndo) );
2063 }
2064 ++nIns;
2065
2066 // if AppendRedline has deleted our redline, we may not keep a
2067 // reference to it
2068 if (IDocumentRedlineAccess::AppendResult::APPENDED != result)
2069 pDestRedl = nullptr;
2070 }
2071 return nIns;
2072 }
2073
2074 /// Merge two documents
2075 tools::Long SwDoc::MergeDoc( const SwDoc& rDoc )
2076 {
2077 if( &rDoc == this )
2078 return 0;
2079
2080 tools::Long nRet = 0;
2081
2082 GetIDocumentUndoRedo().StartUndo(SwUndoId::EMPTY, nullptr);
2083
2084 SwDoc& rSrcDoc = const_cast<SwDoc&>(rDoc);
2085 bool bSrcModified = rSrcDoc.getIDocumentState().IsModified();
2086
2087 RedlineFlags eSrcRedlMode = rSrcDoc.getIDocumentRedlineAccess().GetRedlineFlags();
2088 rSrcDoc.getIDocumentRedlineAccess().SetRedlineFlags( RedlineFlags::ShowDelete );
2089 getIDocumentRedlineAccess().SetRedlineFlags( RedlineFlags::ShowDelete );
2090
2091 CompareMainText aD0(rSrcDoc, false);
2092 CompareMainText aD1(*this, false);
2093 aD1.CompareLines( aD0 );
2094 if( !aD1.HasDiffs( aD0 ) )
2095 {
2096 // we want to get all redlines from the SourceDoc
2097
2098 // look for all insert redlines from the SourceDoc and determine their position in the DestDoc
2099 std::vector<SaveMergeRedline> vRedlines;
2100 const SwRedlineTable& rSrcRedlTable = rSrcDoc.getIDocumentRedlineAccess().GetRedlineTable();
2101 SwNodeOffset nEndOfExtra = rSrcDoc.GetNodes().GetEndOfExtras().GetIndex();
2102 SwNodeOffset nMyEndOfExtra = GetNodes().GetEndOfExtras().GetIndex();
2103 for(const SwRangeRedline* pRedl : rSrcRedlTable)
2104 {
2105 SwNodeOffset nNd = pRedl->GetPoint()->GetNodeIndex();
2106 RedlineType eType = pRedl->GetType();
2107 if( nEndOfExtra < nNd &&
2108 ( RedlineType::Insert == eType || RedlineType::Delete == eType ))
2109 {
2110 const SwNode* pDstNd = GetNodes()[
2111 nMyEndOfExtra + nNd - nEndOfExtra ];
2112
2113 // Found the position.
2114 // Then we also have to insert the redline to the line in the DestDoc.
2115 vRedlines.emplace_back(*pDstNd, *pRedl);
2116 }
2117 }
2118
2119 if( !vRedlines.empty() )
2120 {
2121 // Carry over all into DestDoc
2122 rSrcDoc.getIDocumentRedlineAccess().SetRedlineFlags(RedlineFlags::ShowInsert | RedlineFlags::ShowDelete);
2123
2124 getIDocumentRedlineAccess().SetRedlineFlags(
2125 RedlineFlags::On |
2126 RedlineFlags::ShowInsert |
2127 RedlineFlags::ShowDelete);
2128
2129 SwPaM* pLastDestRedline(nullptr);
2130 for(SaveMergeRedline& rRedline: vRedlines)
2131 {
2132 nRet += rRedline.InsertRedline(pLastDestRedline);
2133 pLastDestRedline = rRedline.pDestRedl;
2134 }
2135 }
2136 }
2137
2138 rSrcDoc.getIDocumentRedlineAccess().SetRedlineFlags( eSrcRedlMode );
2139 if( !bSrcModified )
2140 rSrcDoc.getIDocumentState().ResetModified();
2141
2142 getIDocumentRedlineAccess().SetRedlineFlags(RedlineFlags::ShowInsert | RedlineFlags::ShowDelete);
2143
2144 GetIDocumentUndoRedo().EndUndo(SwUndoId::EMPTY, nullptr);
2145
2146 return nRet;
2147 }
2148
2149 LineArrayComparator::LineArrayComparator( const CompareData &rD1,
2150 const CompareData &rD2, int nStt1,
2151 int nEnd1, int nStt2, int nEnd2 )
2152 : m_rData1( rD1 ), m_rData2( rD2 ), m_nFirst1( nStt1 ), m_nFirst2( nStt2 )
2153 {
2154 m_nLen1 = nEnd1 - nStt1;
2155 m_nLen2 = nEnd2 - nStt2;
2156 }
2157
2158 bool LineArrayComparator::Compare( int nIdx1, int nIdx2 ) const
2159 {
2160 if( nIdx1 < 0 || nIdx2 < 0 || nIdx1 >= m_nLen1 || nIdx2 >= m_nLen2 )
2161 {
2162 OSL_ENSURE( false, "Index out of range!" );
2163 return false;
2164 }
2165
2166 const SwTextNode *pTextNd1 = m_rData1.GetLine( m_nFirst1 + nIdx1 ).GetNode().GetTextNode();
2167 const SwTextNode *pTextNd2 = m_rData2.GetLine( m_nFirst2 + nIdx2 ).GetNode().GetTextNode();
2168
2169 if( !pTextNd1 || !pTextNd2
2170 || ( CmpOptions.bUseRsid && !pTextNd1->CompareParRsid( *pTextNd2 ) ) )
2171 {
2172 return false;
2173 }
2174
2175 const sal_Int32 nPar1Len = pTextNd1->Len();
2176 const sal_Int32 nPar2Len = pTextNd2->Len();
2177
2178 if( std::min( nPar1Len, nPar2Len ) * 3 < std::max( nPar1Len, nPar2Len ) )
2179 {
2180 return false;
2181 }
2182
2183 sal_Int32 nBorderLen = ( nPar1Len + nPar2Len )/16;
2184
2185 if( nBorderLen < 3 )
2186 {
2187 nBorderLen = std::min<sal_Int32>( 3, std::min( nPar1Len, nPar2Len ) );
2188 }
2189
2190 std::set<unsigned> aHashes;
2191 unsigned nHash = 0;
2192 unsigned nMul = 251;
2193 unsigned nPow = 1;
2194 sal_Int32 i;
2195
2196 for( i = 0; i < nBorderLen - 1; i++ )
2197 {
2198 nPow *= nMul;
2199 }
2200 for( i = 0; i < nBorderLen; i++ )
2201 {
2202 nHash = nHash*nMul + pTextNd1->GetText()[i];
2203 }
2204 aHashes.insert( nHash );
2205 for( ; i < nPar1Len; i++ )
2206 {
2207 nHash = nHash - nPow*pTextNd1->GetText()[ i - nBorderLen ];
2208 nHash = nHash*nMul + pTextNd1->GetText()[ i ];
2209
2210 aHashes.insert( nHash );
2211 }
2212
2213 nHash = 0;
2214 for( i = 0; i < nBorderLen; i++ )
2215 {
2216 nHash = nHash*nMul + pTextNd2->GetText()[ i ];
2217 }
2218
2219 if( aHashes.find( nHash ) != aHashes.end() )
2220 {
2221 return true;
2222 }
2223
2224 for( ; i < nPar2Len; i++ )
2225 {
2226 nHash = nHash - nPow*pTextNd2->GetText()[ i - nBorderLen ];
2227 nHash = nHash*nMul + pTextNd2->GetText()[ i ];
2228 if( aHashes.find( nHash ) != aHashes.end() )
2229 {
2230 return true;
2231 }
2232 }
2233 return false;
2234 }
2235
2236 bool CharArrayComparator::Compare( int nIdx1, int nIdx2 ) const
2237 {
2238 if( nIdx1 < 0 || nIdx2 < 0 || nIdx1 >= GetLen1() || nIdx2 >= GetLen2() )
2239 {
2240 OSL_ENSURE( false, "Index out of range!" );
2241 return false;
2242 }
2243
2244 return ( !CmpOptions.bUseRsid
2245 || m_pTextNode1->CompareRsid( *m_pTextNode2, nIdx1 + 1, nIdx2 + 1 ) )
2246 && m_pTextNode1->GetText()[ nIdx1 ] == m_pTextNode2->GetText()[ nIdx2 ];
2247 }
2248
2249 WordArrayComparator::WordArrayComparator( const SwTextNode *pNode1,
2250 const SwTextNode *pNode2 )
2251 : m_pTextNode1( pNode1 ), m_pTextNode2( pNode2 )
2252 {
2253 m_pPos1.reset( new int[ m_pTextNode1->GetText().getLength() + 1 ] );
2254 m_pPos2.reset( new int[ m_pTextNode2->GetText().getLength() + 1 ] );
2255
2256 CalcPositions( m_pPos1.get(), m_pTextNode1, m_nCount1 );
2257 CalcPositions( m_pPos2.get(), m_pTextNode2, m_nCount2 );
2258 }
2259
2260 bool WordArrayComparator::Compare( int nIdx1, int nIdx2 ) const
2261 {
2262 int nLen = m_pPos1[ nIdx1 + 1 ] - m_pPos1[ nIdx1 ];
2263 if( nLen != m_pPos2[ nIdx2 + 1 ] - m_pPos2[ nIdx2 ] )
2264 {
2265 return false;
2266 }
2267 for( int i = 0; i < nLen; i++)
2268 {
2269 if( m_pTextNode1->GetText()[ m_pPos1[ nIdx1 ] + i ]
2270 != m_pTextNode2->GetText()[ m_pPos2[ nIdx2 ] + i ]
2271 || ( CmpOptions.bUseRsid && !m_pTextNode1->CompareRsid( *m_pTextNode2,
2272 m_pPos1[ nIdx1 ] + i, m_pPos2[ nIdx2 ] + i ) ) )
2273 {
2274 return false;
2275 }
2276 }
2277 return true;
2278 }
2279
2280 int WordArrayComparator::GetCharSequence( const int *pWordLcs1,
2281 const int *pWordLcs2, int *pSubseq1, int *pSubseq2, int nLcsLen )
2282 {
2283 int nLen = 0;
2284 for( int i = 0; i < nLcsLen; i++ )
2285 {
2286 // Check for hash collisions
2287 if( m_pPos1[ pWordLcs1[i] + 1 ] - m_pPos1[ pWordLcs1[i] ]
2288 != m_pPos2[ pWordLcs2[i] + 1 ] - m_pPos2[ pWordLcs2[i] ] )
2289 {
2290 continue;
2291 }
2292 for( int j = 0; j < m_pPos1[pWordLcs1[i]+1] - m_pPos1[pWordLcs1[i]]; j++)
2293 {
2294 pSubseq1[ nLen ] = m_pPos1[ pWordLcs1[i] ] + j;
2295 pSubseq2[ nLen ] = m_pPos2[ pWordLcs2[i] ] + j;
2296
2297 if( m_pTextNode1->GetText()[ m_pPos1[ pWordLcs1[i] ] + j ]
2298 != m_pTextNode2->GetText()[ m_pPos2[ pWordLcs2[i] ] + j ] )
2299 {
2300 nLen -= j;
2301 break;
2302 }
2303
2304 nLen++;
2305 }
2306 }
2307 return nLen;
2308 }
2309
2310 void WordArrayComparator::CalcPositions( int *pPos, const SwTextNode *pTextNd,
2311 int &nCnt )
2312 {
2313 nCnt = -1;
2314 for (int i = 0; i <= pTextNd->GetText().getLength(); ++i)
2315 {
2316 if (i == 0 || i == pTextNd->GetText().getLength()
2317 || !rtl::isAsciiAlphanumeric( pTextNd->GetText()[ i - 1 ])
2318 || !rtl::isAsciiAlphanumeric( pTextNd->GetText()[ i ]))
2319 { // Begin new word
2320 nCnt++;
2321 pPos[ nCnt ] = i;
2322 }
2323 }
2324 }
2325
2326 int CommonSubseq::FindLCS( int *pLcs1, int *pLcs2, int nStt1, int nEnd1,
2327 int nStt2, int nEnd2 )
2328 {
2329 int nLen1 = nEnd1 ? nEnd1 - nStt1 : m_rComparator.GetLen1();
2330 int nLen2 = nEnd2 ? nEnd2 - nStt2 : m_rComparator.GetLen2();
2331
2332 assert( nLen1 >= 0 );
2333 assert( nLen2 >= 0 );
2334
2335 std::unique_ptr<int*[]> pLcs( new int*[ nLen1 + 1 ] );
2336 pLcs[ 0 ] = m_pData.get();
2337
2338 for( int i = 1; i < nLen1 + 1; i++ )
2339 pLcs[ i ] = pLcs[ i - 1 ] + nLen2 + 1;
2340
2341 for( int i = 0; i <= nLen1; i++ )
2342 pLcs[i][0] = 0;
2343
2344 for( int j = 0; j <= nLen2; j++ )
2345 pLcs[0][j] = 0;
2346
2347 // Find lcs
2348 for( int i = 1; i <= nLen1; i++ )
2349 {
2350 for( int j = 1; j <= nLen2; j++ )
2351 {
2352 if( m_rComparator.Compare( nStt1 + i - 1, nStt2 + j - 1 ) )
2353 pLcs[i][j] = pLcs[i - 1][j - 1] + 1;
2354 else
2355 pLcs[i][j] = std::max( pLcs[i][j - 1], pLcs[i - 1][j] );
2356 }
2357 }
2358
2359 int nLcsLen = pLcs[ nLen1 ][ nLen2 ];
2360
2361 // Recover the lcs in the two sequences
2362 if( pLcs1 && pLcs2 )
2363 {
2364 int nIdx1 = nLen1;
2365 int nIdx2 = nLen2;
2366 int nIdx = nLcsLen - 1;
2367
2368 while( nIdx1 > 0 && nIdx2 > 0 )
2369 {
2370 if( pLcs[ nIdx1 ][ nIdx2 ] == pLcs[ nIdx1 - 1 ][ nIdx2 ] )
2371 nIdx1--;
2372 else if( pLcs[ nIdx1 ][ nIdx2 ] == pLcs[ nIdx1 ][ nIdx2 - 1 ] )
2373 nIdx2--;
2374 else
2375 {
2376 nIdx1--;
2377 nIdx2--;
2378 pLcs1[ nIdx ] = nIdx1 + nStt1;
2379 pLcs2[ nIdx ] = nIdx2 + nStt2;
2380 nIdx--;
2381 }
2382 }
2383 }
2384
2385 return nLcsLen;
2386 }
2387
2388 int CommonSubseq::IgnoreIsolatedPieces( int *pLcs1, int *pLcs2, int nLen1,
2389 int nLen2, int nLcsLen, int nPieceLen )
2390 {
2391 if( !nLcsLen )
2392 {
2393 return 0;
2394 }
2395
2396 int nNext = 0;
2397
2398 // Don't ignore text at the beginning of the paragraphs
2399 if( pLcs1[ 0 ] == 0 && pLcs2[ 0 ] == 0 )
2400 {
2401 while( nNext < nLcsLen - 1 && pLcs1[ nNext ] + 1 == pLcs1[ nNext + 1 ]
2402 && pLcs2[ nNext ] + 1 == pLcs2[ nNext + 1 ] )
2403 {
2404 nNext++;
2405 }
2406 nNext++;
2407 }
2408
2409 int nCnt = 1;
2410
2411 for( int i = nNext; i < nLcsLen; i++ )
2412 {
2413 if( i != nLcsLen - 1 && pLcs1[ i ] + 1 == pLcs1[ i + 1 ]
2414 && pLcs2[ i ] + 1 == pLcs2[ i + 1 ] )
2415 {
2416 nCnt++;
2417 }
2418 else
2419 {
2420 if( nCnt > nPieceLen
2421 // Don't ignore text at the end of the paragraphs
2422 || ( i == nLcsLen - 1
2423 && pLcs1[i] == nLen1 - 1 && pLcs2[i] == nLen2 - 1 ))
2424 {
2425 for( int j = i + 1 - nCnt; j <= i; j++ )
2426 {
2427 pLcs2[ nNext ] = pLcs2[ j ];
2428 pLcs1[ nNext ] = pLcs1[ j ];
2429 nNext++;
2430 }
2431 }
2432 nCnt = 1;
2433 }
2434 }
2435
2436 return nNext;
2437 }
2438
2439 LgstCommonSubseq::LgstCommonSubseq( ArrayComparator &rComparator )
2440 : CommonSubseq( rComparator, CUTOFF )
2441 {
2442 m_pBuff1.reset( new int[ rComparator.GetLen2() + 1 ] );
2443 m_pBuff2.reset( new int[ rComparator.GetLen2() + 1 ] );
2444
2445 m_pL1.reset( new int[ rComparator.GetLen2() + 1 ] );
2446 m_pL2.reset( new int[ rComparator.GetLen2() + 1 ] );
2447 }
2448
2449 void LgstCommonSubseq::FindL( int *pL, int nStt1, int nEnd1,
2450 int nStt2, int nEnd2 )
2451 {
2452 int nLen1 = nEnd1 ? nEnd1 - nStt1 : m_rComparator.GetLen1();
2453 int nLen2 = nEnd2 ? nEnd2 - nStt2 : m_rComparator.GetLen2();
2454
2455 int *currL = m_pBuff1.get();
2456 int *prevL = m_pBuff2.get();
2457
2458 // Avoid memory corruption
2459 if( nLen2 > m_rComparator.GetLen2() )
2460 {
2461 assert( false );
2462 return;
2463 }
2464
2465 memset( m_pBuff1.get(), 0, sizeof( m_pBuff1[0] ) * ( nLen2 + 1 ) );
2466 memset( m_pBuff2.get(), 0, sizeof( m_pBuff2[0] ) * ( nLen2 + 1 ) );
2467
2468 // Find lcs
2469 for( int i = 1; i <= nLen1; i++ )
2470 {
2471 for( int j = 1; j <= nLen2; j++ )
2472 {
2473 if( m_rComparator.Compare( nStt1 + i - 1, nStt2 + j - 1 ) )
2474 currL[j] = prevL[j - 1] + 1;
2475 else
2476 currL[j] = std::max( currL[j - 1], prevL[j] );
2477 }
2478 std::swap( currL, prevL );
2479 }
2480 memcpy( pL, prevL, ( nLen2 + 1 ) * sizeof( *prevL ) );
2481 }
2482
2483 int LgstCommonSubseq::HirschbergLCS( int *pLcs1, int *pLcs2, int nStt1,
2484 int nEnd1, int nStt2, int nEnd2 )
2485 {
2486 static int nLen1;
2487 static int nLen2;
2488 nLen1 = nEnd1 - nStt1;
2489 nLen2 = nEnd2 - nStt2;
2490
2491 if( ( nLen1 + 1 ) * ( nLen2 + 1 ) <= CUTOFF )
2492 {
2493 if( !nLen1 || !nLen2 )
2494 {
2495 return 0;
2496 }
2497 return FindLCS(pLcs1, pLcs2, nStt1, nEnd1, nStt2, nEnd2);
2498 }
2499
2500 int nMid = nLen1/2;
2501
2502 FindL( m_pL1.get(), nStt1, nStt1 + nMid, nStt2, nEnd2 );
2503 FindL( m_pL2.get(), nStt1 + nMid, nEnd1, nStt2, nEnd2 );
2504
2505 int nMaxPos = 0;
2506 static int nMaxVal;
2507 nMaxVal = -1;
2508
2509 static int i;
2510 for( i = 0; i <= nLen2; i++ )
2511 {
2512 if( m_pL1[i] + ( m_pL2[nLen2] - m_pL2[i] ) > nMaxVal )
2513 {
2514 nMaxPos = i;
2515 nMaxVal = m_pL1[i]+( m_pL2[nLen2] - m_pL2[i] );
2516 }
2517 }
2518
2519 int nRet = HirschbergLCS( pLcs1, pLcs2, nStt1, nStt1 + nMid,
2520 nStt2, nStt2 + nMaxPos );
2521 nRet += HirschbergLCS( pLcs1 + nRet, pLcs2 + nRet, nStt1 + nMid, nEnd1,
2522 nStt2 + nMaxPos, nEnd2 );
2523
2524 return nRet;
2525 }
2526
2527 int LgstCommonSubseq::Find( int *pSubseq1, int *pSubseq2 )
2528 {
2529 int nStt = 0;
2530 int nCutEnd = 0;
2531 int nEnd1 = m_rComparator.GetLen1();
2532 int nEnd2 = m_rComparator.GetLen2();
2533
2534 // Check for corresponding lines in the beginning of the sequences
2535 while( nStt < nEnd1 && nStt < nEnd2 && m_rComparator.Compare( nStt, nStt ) )
2536 {
2537 pSubseq1[ nStt ] = nStt;
2538 pSubseq2[ nStt ] = nStt;
2539 nStt++;
2540 }
2541
2542 pSubseq1 += nStt;
2543 pSubseq2 += nStt;
2544
2545 // Check for corresponding lines in the end of the sequences
2546 while( nStt < nEnd1 && nStt < nEnd2
2547 && m_rComparator.Compare( nEnd1 - 1, nEnd2 - 1 ) )
2548 {
2549 nCutEnd++;
2550 nEnd1--;
2551 nEnd2--;
2552 }
2553
2554 int nLen = HirschbergLCS( pSubseq1, pSubseq2, nStt, nEnd1, nStt, nEnd2 );
2555
2556 for( int i = 0; i < nCutEnd; i++ )
2557 {
2558 pSubseq1[ nLen + i ] = nEnd1 + i;
2559 pSubseq2[ nLen + i ] = nEnd2 + i;
2560 }
2561
2562 return nStt + nLen + nCutEnd;
2563 }
2564
2565 int FastCommonSubseq::FindFastCS( int *pSeq1, int *pSeq2, int nStt1,
2566 int nEnd1, int nStt2, int nEnd2 )
2567 {
2568 int nCutBeg = 0;
2569 int nCutEnd = 0;
2570
2571 // Check for corresponding lines in the beginning of the sequences
2572 while( nStt1 < nEnd1 && nStt2 < nEnd2 && m_rComparator.Compare( nStt1, nStt2 ) )
2573 {
2574 pSeq1[ nCutBeg ] = nStt1++;
2575 pSeq2[ nCutBeg ] = nStt2++;
2576 nCutBeg++;
2577 }
2578
2579 pSeq1 += nCutBeg;
2580 pSeq2 += nCutBeg;
2581
2582 // Check for corresponding lines in the end of the sequences
2583 while( nStt1 < nEnd1 && nStt2 < nEnd2
2584 && m_rComparator.Compare( nEnd1 - 1, nEnd2 - 1 ) )
2585 {
2586 nCutEnd++;
2587 nEnd1--;
2588 nEnd2--;
2589 }
2590
2591 int nLen1 = nEnd1 - nStt1;
2592 int nLen2 = nEnd2 - nStt2;
2593
2594 // Return if a sequence is empty
2595 if( nLen1 <= 0 || nLen2 <= 0 )
2596 {
2597 for( int i = 0; i < nCutEnd; i++ )
2598 {
2599 pSeq1[ i ] = nEnd1 + i;
2600 pSeq2[ i ] = nEnd2 + i;
2601 }
2602 return nCutBeg + nCutEnd;
2603 }
2604
2605 // Cut to LCS for small values
2606 if( nLen1 < 3 || nLen2 < 3 || ( nLen1 + 1 ) * ( nLen2 + 1 ) <= CUTOFF )
2607 {
2608 int nLcsLen = FindLCS( pSeq1, pSeq2, nStt1, nEnd1, nStt2, nEnd2);
2609
2610 for( int i = 0; i < nCutEnd; i++ )
2611 {
2612 pSeq1[ nLcsLen + i ] = nEnd1 + i;
2613 pSeq2[ nLcsLen + i ] = nEnd2 + i;
2614 }
2615 return nCutBeg + nLcsLen + nCutEnd;
2616 }
2617
2618 int nMid1 = nLen1/2;
2619 int nMid2 = nLen2/2;
2620
2621 int nRad;
2622 int nPos1 = -1, nPos2 = -1;
2623
2624 // Find a point of correspondence in the middle of the sequences
2625 for( nRad = 0; nRad*nRad < std::min( nMid1, nMid2 ); nRad++ )
2626 {
2627 // Search to the left and to the right of the middle of the first sequence
2628 for( int i = nMid1 - nRad; i <= nMid1 + nRad; i++ )
2629 {
2630 if( m_rComparator.Compare( nStt1 + i, nStt2 + nMid2 - nRad ) )
2631 {
2632 nPos1 = nStt1 + i;
2633 nPos2 = nStt2 + nMid2 - nRad;
2634 break;
2635 }
2636 if( m_rComparator.Compare( nStt1 + i, nStt2 + nMid2 + nRad ) )
2637 {
2638 nPos1 = nStt1 + i;
2639 nPos2 = nStt2 + nMid2 - nRad;
2640 break;
2641 }
2642 }
2643 // Search to the left and to the right of the middle of the second sequence
2644 for( int i = nMid2 - nRad; i <= nMid2 + nRad; i++ )
2645 {
2646 if( m_rComparator.Compare( nStt2 + nMid2 - nRad, nStt2 + i ) )
2647 {
2648 nPos2 = nStt2 + i;
2649 nPos1 = nStt1 + nMid1 - nRad;
2650 break;
2651 }
2652 if( m_rComparator.Compare( nStt2 + nMid2 - nRad, nStt2 + i ) )
2653 {
2654 nPos2 = nStt2 + i;
2655 nPos1 = nStt1 + nMid1 - nRad;
2656 break;
2657 }
2658 }
2659 }
2660
2661 // return if no point of correspondence found
2662 if( nPos1 == -1 )
2663 {
2664 for( int i = 0; i < nCutEnd; i++ )
2665 {
2666 pSeq1[ i ] = nEnd1 + i;
2667 pSeq2[ i ] = nEnd2 + i;
2668 }
2669 return nCutBeg + nCutEnd;
2670 }
2671
2672 // Run the same on the sequences to the left of the correspondence point
2673 int nLen = FindFastCS( pSeq1, pSeq2, nStt1, nPos1, nStt2, nPos2 );
2674
2675 pSeq1[ nLen ] = nPos1;
2676 pSeq2[ nLen ] = nPos2;
2677
2678 // Run the same on the sequences to the right of the correspondence point
2679 nLen += FindFastCS( pSeq1 + nLen + 1, pSeq2 + nLen + 1,
2680 nPos1 + 1, nEnd1, nPos2 + 1, nEnd2 ) + 1;
2681
2682 for( int i = 0; i < nCutEnd; i++ )
2683 {
2684 pSeq1[ nLen + i ] = nEnd1 + i;
2685 pSeq2[ nLen + i ] = nEnd2 + i;
2686 }
2687
2688 return nLen + nCutBeg + nCutEnd;
2689 }
2690
2691 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
FREE OFFICE SUITE