LibreOffice Module sw (master) 1
doccomp.cxx
Go to the documentation of this file.
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>
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
53using namespace ::com::sun::star;
54
55using std::vector;
56
57namespace {
58
59class SwCompareLine final
60{
61 const SwNode* m_pNode;
62public:
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
86class CompareData
87{
88protected:
90private:
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
107public:
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
154class CompareMainText : public CompareData
155{
156public:
157 CompareMainText(SwDoc &rD, bool bRecordDiff)
158 : CompareData(rD, bRecordDiff)
159 {
160 }
161
162 virtual const SwNode& GetEndOfContent() override
163 {
165 }
166};
167
168class CompareFrameFormatText : public CompareData
169{
170 const SwNodeIndex &m_rIndex;
171public:
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
184class 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
199public:
200 explicit Hash( sal_uLong nSize );
201
202 void CalcHashValue( CompareData& rData );
203
204 sal_uLong GetCount() const { return m_nCount; }
205};
206
207class Compare
208{
209public:
210 class MovedData
211 {
212 std::unique_ptr<sal_uLong[]> m_pIndex;
213 std::unique_ptr<sal_uLong[]> m_pLineNum;
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
224private:
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
247public:
248 Compare( sal_uLong nDiff, CompareData& rData1, CompareData& rData2 );
249};
250
251class ArrayComparator
252{
253public:
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
262class LineArrayComparator : public ArrayComparator
263{
264private:
265 int m_nLen1, m_nLen2;
266 const CompareData &m_rData1, &m_rData2;
267 int m_nFirst1, m_nFirst2;
268
269public:
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
278class WordArrayComparator : public ArrayComparator
279{
280private:
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
287public:
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
297class CharArrayComparator : public ArrayComparator
298{
299private:
300 const SwTextNode *m_pTextNode1, *m_pTextNode2;
301
302public:
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
314struct CmpOptionsContainer
315{
316 SwCompareMode eCmpMode;
317 int nIgnoreLen;
318 bool bUseRsid;
319};
320
321}
322
323static CmpOptionsContainer CmpOptions;
324
325namespace {
326
327class CommonSubseq
328{
329private:
330 std::unique_ptr<int[]> m_pData;
331
332protected:
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
344public:
345 static int IgnoreIsolatedPieces( int *pLcs1, int *pLcs2, int nLen1, int nLen2,
346 int nLcsLen, int nPieceLen );
347};
348
350class LgstCommonSubseq: public CommonSubseq
351{
352private:
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
362public:
363 explicit LgstCommonSubseq( ArrayComparator &rComparator );
364
365 int Find( int *pSubseq1, int *pSubseq2 );
366};
367
369class FastCommonSubseq: private CommonSubseq
370{
371private:
372 static const int CUTOFF = 2056;
373
374 int FindFastCS( int *pSeq1, int *pSeq2, int nStt1, int nEnd1,
375 int nStt2, int nEnd2 );
376
377public:
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
392CompareData::~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
408void 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
419void 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
430void 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
446sal_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
477bool 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
496Hash::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
545void 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
575Compare::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
611void 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
621void 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
645void 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;
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
757Compare::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
784Compare::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
797void 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
847sal_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
935namespace
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
1005void Compare::ShiftBoundaries( CompareData& rData1, CompareData& rData2 )
1006{
1007 lcl_ShiftBoundariesOneway(&rData1, &rData2);
1008 lcl_ShiftBoundariesOneway(&rData2, &rData1);
1009}
1010
1011sal_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
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
1050const 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
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
1072bool SwCompareLine::Compare( const SwCompareLine& rLine ) const
1073{
1074 return CompareNode( *m_pNode, *rLine.m_pNode );
1075}
1076
1077namespace
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
1100bool 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
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 {
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
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
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
1195OUString 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
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 {
1219 if( rSect.IsProtect() )
1220 sRet += OUString::number(
1221 sal_Int32(rSNd.EndOfSectionIndex() - rSNd.GetIndex()) );
1222 break;
1223
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
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
1253sal_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
1261bool 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
1274bool 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(),
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
1411SwNodeOffset 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
1429SwNodeOffset 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
1447void 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
1500void 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
1511void 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());
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
1575void 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
1628void 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 {
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
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
1784typedef std::shared_ptr<CompareData> CompareDataPtr;
1785typedef std::pair<CompareDataPtr, CompareDataPtr> CompareDataPtrPair;
1786typedef std::vector<CompareDataPtrPair> Comparators;
1787
1788namespace
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 SwFrameFormats *pSrcFrameFormats = rSrcDoc.GetSpzFrameFormats();
1799 const SwFrameFormats *pDestFrameFormats = rDestDoc.GetSpzFrameFormats();
1800 if (pSrcFrameFormats->size() == pDestFrameFormats->size())
1801 {
1802 for (size_t i = 0; i < pSrcFrameFormats->size(); ++i)
1803 {
1804 const SwFrameFormat& rSrcFormat = *(*pSrcFrameFormats)[i];
1805 const SwFrameFormat& 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
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 {
1846 CmpOptions.bUseRsid = true;
1847 CmpOptions.nIgnoreLen = 2;
1848 }
1849 else
1850 {
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();
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 {
1885
1886 for (auto& a : aComparisons)
1887 {
1888 CompareData& rD1 = *a.second;
1889 rD1.SetRedlinesToDoc( !bDocWasModified );
1890 }
1892 }
1893
1894 rSrcDoc.getIDocumentRedlineAccess().SetRedlineFlags( eSrcRedlMode );
1896
1897 if( !bSrcModified )
1898 rSrcDoc.getIDocumentState().ResetModified();
1899
1900 GetIDocumentUndoRedo().EndUndo(SwUndoId::EMPTY, nullptr);
1901
1902 return nRet;
1903}
1904
1905namespace
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
1916SaveMergeRedline::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
1940sal_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
1955
1956 pSrcRedl->GetDoc().getIDocumentContentOperations().CopyRange(
1957 *const_cast<SwPaM*>(static_cast<const SwPaM*>(pSrcRedl)),
1958 *pDestRedl->GetPoint(), SwCopyFlags::CheckPosInFly);
1959
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();
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 {
1995 break;
1996
1999 delete pDestRedl;
2000 pDestRedl = nullptr;
2001 [[fallthrough]];
2002
2005 n = rRedlineTable.size();
2006 break;
2007
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
2033 }
2034 break;
2035
2037 *pDEnd = *pRStt;
2038 break;
2039
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)
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
2069 pDestRedl = nullptr;
2070 }
2071 return nIns;
2072}
2073
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();
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
2123
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
2143
2144 GetIDocumentUndoRedo().EndUndo(SwUndoId::EMPTY, nullptr);
2145
2146 return nRet;
2147}
2148
2149LineArrayComparator::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
2158bool 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
2236bool 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
2249WordArrayComparator::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
2260bool 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
2280int 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
2310void 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
2326int 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
2388int 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
2439LgstCommonSubseq::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
2449void 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 int *tmp = currL;
2479 currL = prevL;
2480 prevL = tmp;
2481 }
2482 memcpy( pL, prevL, ( nLen2 + 1 ) * sizeof( *prevL ) );
2483}
2484
2485int LgstCommonSubseq::HirschbergLCS( int *pLcs1, int *pLcs2, int nStt1,
2486 int nEnd1, int nStt2, int nEnd2 )
2487{
2488 static int nLen1;
2489 static int nLen2;
2490 nLen1 = nEnd1 - nStt1;
2491 nLen2 = nEnd2 - nStt2;
2492
2493 if( ( nLen1 + 1 ) * ( nLen2 + 1 ) <= CUTOFF )
2494 {
2495 if( !nLen1 || !nLen2 )
2496 {
2497 return 0;
2498 }
2499 return FindLCS(pLcs1, pLcs2, nStt1, nEnd1, nStt2, nEnd2);
2500 }
2501
2502 int nMid = nLen1/2;
2503
2504 FindL( m_pL1.get(), nStt1, nStt1 + nMid, nStt2, nEnd2 );
2505 FindL( m_pL2.get(), nStt1 + nMid, nEnd1, nStt2, nEnd2 );
2506
2507 int nMaxPos = 0;
2508 static int nMaxVal;
2509 nMaxVal = -1;
2510
2511 static int i;
2512 for( i = 0; i <= nLen2; i++ )
2513 {
2514 if( m_pL1[i] + ( m_pL2[nLen2] - m_pL2[i] ) > nMaxVal )
2515 {
2516 nMaxPos = i;
2517 nMaxVal = m_pL1[i]+( m_pL2[nLen2] - m_pL2[i] );
2518 }
2519 }
2520
2521 int nRet = HirschbergLCS( pLcs1, pLcs2, nStt1, nStt1 + nMid,
2522 nStt2, nStt2 + nMaxPos );
2523 nRet += HirschbergLCS( pLcs1 + nRet, pLcs2 + nRet, nStt1 + nMid, nEnd1,
2524 nStt2 + nMaxPos, nEnd2 );
2525
2526 return nRet;
2527}
2528
2529int LgstCommonSubseq::Find( int *pSubseq1, int *pSubseq2 )
2530{
2531 int nStt = 0;
2532 int nCutEnd = 0;
2533 int nEnd1 = m_rComparator.GetLen1();
2534 int nEnd2 = m_rComparator.GetLen2();
2535
2536 // Check for corresponding lines in the beginning of the sequences
2537 while( nStt < nEnd1 && nStt < nEnd2 && m_rComparator.Compare( nStt, nStt ) )
2538 {
2539 pSubseq1[ nStt ] = nStt;
2540 pSubseq2[ nStt ] = nStt;
2541 nStt++;
2542 }
2543
2544 pSubseq1 += nStt;
2545 pSubseq2 += nStt;
2546
2547 // Check for corresponding lines in the end of the sequences
2548 while( nStt < nEnd1 && nStt < nEnd2
2549 && m_rComparator.Compare( nEnd1 - 1, nEnd2 - 1 ) )
2550 {
2551 nCutEnd++;
2552 nEnd1--;
2553 nEnd2--;
2554 }
2555
2556 int nLen = HirschbergLCS( pSubseq1, pSubseq2, nStt, nEnd1, nStt, nEnd2 );
2557
2558 for( int i = 0; i < nCutEnd; i++ )
2559 {
2560 pSubseq1[ nLen + i ] = nEnd1 + i;
2561 pSubseq2[ nLen + i ] = nEnd2 + i;
2562 }
2563
2564 return nStt + nLen + nCutEnd;
2565}
2566
2567int FastCommonSubseq::FindFastCS( int *pSeq1, int *pSeq2, int nStt1,
2568 int nEnd1, int nStt2, int nEnd2 )
2569{
2570 int nCutBeg = 0;
2571 int nCutEnd = 0;
2572
2573 // Check for corresponding lines in the beginning of the sequences
2574 while( nStt1 < nEnd1 && nStt2 < nEnd2 && m_rComparator.Compare( nStt1, nStt2 ) )
2575 {
2576 pSeq1[ nCutBeg ] = nStt1++;
2577 pSeq2[ nCutBeg ] = nStt2++;
2578 nCutBeg++;
2579 }
2580
2581 pSeq1 += nCutBeg;
2582 pSeq2 += nCutBeg;
2583
2584 // Check for corresponding lines in the end of the sequences
2585 while( nStt1 < nEnd1 && nStt2 < nEnd2
2586 && m_rComparator.Compare( nEnd1 - 1, nEnd2 - 1 ) )
2587 {
2588 nCutEnd++;
2589 nEnd1--;
2590 nEnd2--;
2591 }
2592
2593 int nLen1 = nEnd1 - nStt1;
2594 int nLen2 = nEnd2 - nStt2;
2595
2596 // Return if a sequence is empty
2597 if( nLen1 <= 0 || nLen2 <= 0 )
2598 {
2599 for( int i = 0; i < nCutEnd; i++ )
2600 {
2601 pSeq1[ i ] = nEnd1 + i;
2602 pSeq2[ i ] = nEnd2 + i;
2603 }
2604 return nCutBeg + nCutEnd;
2605 }
2606
2607 // Cut to LCS for small values
2608 if( nLen1 < 3 || nLen2 < 3 || ( nLen1 + 1 ) * ( nLen2 + 1 ) <= CUTOFF )
2609 {
2610 int nLcsLen = FindLCS( pSeq1, pSeq2, nStt1, nEnd1, nStt2, nEnd2);
2611
2612 for( int i = 0; i < nCutEnd; i++ )
2613 {
2614 pSeq1[ nLcsLen + i ] = nEnd1 + i;
2615 pSeq2[ nLcsLen + i ] = nEnd2 + i;
2616 }
2617 return nCutBeg + nLcsLen + nCutEnd;
2618 }
2619
2620 int nMid1 = nLen1/2;
2621 int nMid2 = nLen2/2;
2622
2623 int nRad;
2624 int nPos1 = -1, nPos2 = -1;
2625
2626 // Find a point of correspondence in the middle of the sequences
2627 for( nRad = 0; nRad*nRad < std::min( nMid1, nMid2 ); nRad++ )
2628 {
2629 // Search to the left and to the right of the middle of the first sequence
2630 for( int i = nMid1 - nRad; i <= nMid1 + nRad; i++ )
2631 {
2632 if( m_rComparator.Compare( nStt1 + i, nStt2 + nMid2 - nRad ) )
2633 {
2634 nPos1 = nStt1 + i;
2635 nPos2 = nStt2 + nMid2 - nRad;
2636 break;
2637 }
2638 if( m_rComparator.Compare( nStt1 + i, nStt2 + nMid2 + nRad ) )
2639 {
2640 nPos1 = nStt1 + i;
2641 nPos2 = nStt2 + nMid2 - nRad;
2642 break;
2643 }
2644 }
2645 // Search to the left and to the right of the middle of the second sequence
2646 for( int i = nMid2 - nRad; i <= nMid2 + nRad; i++ )
2647 {
2648 if( m_rComparator.Compare( nStt2 + nMid2 - nRad, nStt2 + i ) )
2649 {
2650 nPos2 = nStt2 + i;
2651 nPos1 = nStt1 + nMid1 - nRad;
2652 break;
2653 }
2654 if( m_rComparator.Compare( nStt2 + nMid2 - nRad, nStt2 + i ) )
2655 {
2656 nPos2 = nStt2 + i;
2657 nPos1 = nStt1 + nMid1 - nRad;
2658 break;
2659 }
2660 }
2661 }
2662
2663 // return if no point of correspondence found
2664 if( nPos1 == -1 )
2665 {
2666 for( int i = 0; i < nCutEnd; i++ )
2667 {
2668 pSeq1[ i ] = nEnd1 + i;
2669 pSeq2[ i ] = nEnd2 + i;
2670 }
2671 return nCutBeg + nCutEnd;
2672 }
2673
2674 // Run the same on the sequences to the left of the correspondence point
2675 int nLen = FindFastCS( pSeq1, pSeq2, nStt1, nPos1, nStt2, nPos2 );
2676
2677 pSeq1[ nLen ] = nPos1;
2678 pSeq2[ nLen ] = nPos2;
2679
2680 // Run the same on the sequences to the right of the correspondence point
2681 nLen += FindFastCS( pSeq1 + nLen + 1, pSeq2 + nLen + 1,
2682 nPos1 + 1, nEnd1, nPos2 + 1, nEnd2 ) + 1;
2683
2684 for( int i = 0; i < nCutEnd; i++ )
2685 {
2686 pSeq1[ nLen + i ] = nEnd1 + i;
2687 pSeq2[ nLen + i ] = nEnd2 + i;
2688 }
2689
2690 return nLen + nCutBeg + nCutEnd;
2691}
2692
2693/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
@ CheckPosInFly
check if target position is in fly anchored at source range
@ ShowDelete
show all deletes
@ On
RedlineFlags on.
@ ShowInsert
show all inserts
@ Ignore
ignore Redlines
double d
virtual bool DeleteRedline(const SwPaM &rPam, bool bSaveInUndo, RedlineType nDelType)=0
virtual std::size_t GetRedlineAuthor()=0
virtual void SetRedlineFlags_intern(RedlineFlags eMode)=0
Set a new redline mode.
virtual const SwRedlineTable & GetRedlineTable() const =0
virtual std::size_t InsertRedlineAuthor(const OUString &rAuthor)=0
virtual AppendResult AppendRedline(SwRangeRedline *pNewRedl, bool bCallDelete)=0
Append a new redline.
virtual void SetRedlineFlags(RedlineFlags eMode)=0
Set a new redline mode.
virtual const SwRangeRedline * GetRedline(const SwPosition &rPos, SwRedlineTable::size_type *pFndPos) const =0
virtual RedlineFlags GetRedlineFlags() const =0
Query the currently set redline mode.
virtual void ResetModified()=0
virtual void SetModified()=0
Must be called manually at changes of format.
virtual bool IsModified() const =0
Changes of document?
virtual sal_Int32 Len() const
Definition: node.cxx:1263
Definition: doc.hxx:194
tools::Long CompareDoc(const SwDoc &rDoc)
Definition: doccomp.cxx:1832
IDocumentState const & getIDocumentState() const
Definition: doc.cxx:400
sal_uInt32 getRsidRoot() const
Definition: doc.cxx:222
IDocumentUndoRedo & GetIDocumentUndoRedo()
Definition: doc.cxx:150
SwNodes & GetNodes()
Definition: doc.hxx:417
IDocumentRedlineAccess const & getIDocumentRedlineAccess() const
Definition: doc.cxx:341
const SwFrameFormats * GetSpzFrameFormats() const
Definition: doc.hxx:752
SwDocShell * GetDocShell()
Definition: doc.hxx:1359
tools::Long MergeDoc(const SwDoc &rDoc)
Merge two documents.
Definition: doccomp.cxx:2075
const SwNodeIndex * GetContentIdx() const
Definition: fmtcntnt.hxx:46
const SwFormatContent & GetContent(bool=true) const
Definition: fmtcntnt.hxx:55
Style of a layout element.
Definition: frmfmt.hxx:62
Specific frame formats (frames, DrawObjects).
size_t size() const
Marks a node in the document model.
Definition: ndindex.hxx:31
const SwNodes & GetNodes() const
Definition: ndindex.hxx:175
SwNode & GetNode() const
Definition: ndindex.hxx:136
SwNodeOffset GetIndex() const
Definition: ndindex.hxx:171
Base class of the Writer document model elements.
Definition: node.hxx:98
SwTextNode * GetTextNode()
Inline methods from Node.hxx.
Definition: ndtxt.hxx:897
SwSectionNode * GetSectionNode()
Definition: node.hxx:656
SwNodeOffset GetIndex() const
Definition: node.hxx:312
bool IsContentNode() const
Definition: node.hxx:677
SwDoc & GetDoc()
Definition: node.hxx:233
bool IsEndNode() const
Definition: node.hxx:681
bool IsStartNode() const
Definition: node.hxx:673
bool IsTableNode() const
Definition: node.hxx:689
const SwStartNode * StartOfSectionNode() const
Definition: node.hxx:153
SwNodeOffset EndOfSectionIndex() const
Definition: node.hxx:726
SwContentNode * GetContentNode()
Definition: node.hxx:664
SwNodeType GetNodeType() const
Definition: node.hxx:166
SwEndNode * GetEndNode()
Definition: node.hxx:632
const SwEndNode * EndOfSectionNode() const
Definition: node.hxx:731
SwNode & GetEndOfExtras() const
This is the last EndNode of a special section.
Definition: ndarr.hxx:163
SwNode & GetEndOfContent() const
Regular ContentSection (i.e. the BodyText).
Definition: ndarr.hxx:165
PaM is Point and Mark: a selection of the document model.
Definition: pam.hxx:187
const SwPosition * GetMark() const
Definition: pam.hxx:263
virtual void SetMark()
Unless this is called, the getter method of Mark will return Point.
Definition: pam.cxx:642
SwPaM * GetPrev()
Definition: pam.hxx:324
SwContentNode * GetPointContentNode() const
Definition: pam.hxx:287
const SwPosition * End() const
Definition: pam.hxx:271
SwPaM * GetNext()
Definition: pam.hxx:320
const SwPosition * GetPoint() const
Definition: pam.hxx:261
const SwPosition * Start() const
Definition: pam.hxx:266
RedlineType GetType(sal_uInt16 nPos=0) const
Definition: docredln.cxx:1940
const SwRedlineData & GetRedlineData(sal_uInt16 nPos=0) const
Definition: docredln.cxx:1963
static constexpr size_type npos
Definition: docary.hxx:223
size_type size() const
Definition: docary.hxx:267
vector_type::size_type size_type
Definition: docary.hxx:222
const SwSection & GetSection() const
Definition: node.hxx:588
OUString const & GetLinkFileName() const
Definition: section.cxx:511
const SwTOXBase * GetTOXBase() const
Definition: section.cxx:583
bool IsProtect() const
Definition: section.cxx:326
SectionType GetType() const
Definition: section.hxx:171
OUString const & GetTypeName() const
Definition: tox.hxx:710
TOXTypes GetType() const
Definition: tox.hxx:722
const OUString & GetTitle() const
Definition: tox.hxx:704
SwTextNode is a paragraph in the document model.
Definition: ndtxt.hxx:111
OUString GetExpandText(SwRootFrame const *pLayout, const sal_Int32 nIdx=0, const sal_Int32 nLen=-1, const bool bWithNum=false, const bool bAddSpaceAfterListLabelStr=false, const bool bWithSpacesForLevel=false, const ExpandMode eAdditionalMode=ExpandMode::ExpandFootnote|ExpandMode::HideFieldmarkCommands) const
add 4th optional parameter <bAddSpaceAfterListLabelStr> indicating, when <bWithNum = true> that a spa...
Definition: ndtxt.cxx:3485
virtual sal_Int32 Len() const override
Definition: ndtxt.cxx:290
bool CompareParRsid(const SwTextNode &rTextNode) const
Definition: ndtxt.cxx:5361
bool CompareRsid(const SwTextNode &rTextNode, sal_Int32 nStt1, sal_Int32 nStt2) const
Definition: ndtxt.cxx:5369
const OUString & GetText() const
Definition: ndtxt.hxx:242
RedlineType
SwDoc & m_rDoc
Definition: docbm.cxx:1202
static CmpOptionsContainer CmpOptions
Definition: doccomp.cxx:323
std::pair< CompareDataPtr, CompareDataPtr > CompareDataPtrPair
Definition: doccomp.cxx:1785
std::shared_ptr< CompareData > CompareDataPtr
Definition: doccomp.cxx:1784
std::vector< CompareDataPtrPair > Comparators
Definition: doccomp.cxx:1786
static SwNode * GetEndNode(SwOutlineNodes const *pOutlNds, int nOutlineLevel, SwOutlineNodes::size_type *nOutl)
Definition: docglbl.cxx:103
float y
float x
FmFilterData * m_pData
DocumentType eType
sal_Int32 nIndex
sal_Int64 n
uno_Any a
Sequence< sal_Int8 > aSeq
sal_Int16 m_nCount
std::unique_ptr< sal_Int32[]> pData
SwCompareMode
Definition: modcfg.hxx:88
double getLength(const B2DPolygon &rCandidate)
int i
constexpr std::enable_if_t< std::is_signed_v< T >, std::make_unsigned_t< T > > make_unsigned(T value)
long Long
static void InsertLine(std::vector< SwTableLine * > &rLineArr, SwTableLine *pLine)
Definition: ndtbl1.cxx:169
@ Table
SwTableNode is derived from SwStartNode.
@ Section
SwSectionNode is derived from SwStartNode.
o3tl::strong_int< sal_Int32, struct Tag_SwNodeOffset > SwNodeOffset
Definition: nodeoffset.hxx:16
SwNodeOffset min(const SwNodeOffset &a, const SwNodeOffset &b)
Definition: nodeoffset.hxx:35
SwContentNode * GetNode(SwPaM &rPam, bool &rbFirst, SwMoveFnCollection const &fnMove, bool const bInReadOnly, SwRootFrame const *const i_pLayout)
This function returns the next node in direction of search.
Definition: pam.cxx:1019
SwComparePosition ComparePosition(const T &rStt1, const T &rEnd1, const T &rStt2, const T &rEnd2)
Definition: pam.hxx:122
SwComparePosition
Definition: pam.hxx:109
@ OverlapBehind
Pos1 overlaps Pos2 at the end.
@ CollideEnd
Pos1 end touches at Pos2 start.
@ Behind
Pos1 behind Pos2.
@ OverlapBefore
Pos1 overlaps Pos2 at the beginning.
@ Outside
Pos2 completely contained in Pos1.
@ Before
Pos1 before Pos2.
@ Inside
Pos1 completely contained in Pos2.
@ CollideStart
Pos1 start touches at Pos2 end.
@ Equal
Pos1 is as large as Pos2.
SectionType
Definition: section.hxx:46
sal_uIntPtr sal_uLong
Marks a position in the document model.
Definition: pam.hxx:37
void Adjust(SwNodeOffset nDelta)
Adjust node position, and resets content position to zero.
Definition: pam.cxx:256
SwNode & GetNode() const
Definition: pam.hxx:80
void SetMark(const sw::mark::IMark *pMark)
Definition: pam.hxx:85
void Assign(const SwNode &rNd, SwNodeOffset nDelta, sal_Int32 nContentOffset=0)
These all set both nNode and nContent.
Definition: pam.cxx:230
void SetContent(sal_Int32 nContentIndex)
Set content index, only valid to call this if the position points to a SwContentNode subclass.
Definition: pam.cxx:266
SwNodeOffset GetNodeIndex() const
Definition: pam.hxx:77
sal_Int32 GetContentIndex() const
Definition: pam.hxx:84
UNDERLYING_TYPE get() const
#define SW_MOD()
Definition: swmodule.hxx:256
Any result