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 
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;
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:
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 
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 
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 
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 
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;
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 
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 
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 
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()->nContent = 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()->nContent = 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()->nContent = 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);
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()->nNode, -1 );
1570  *pCorr->GetPoint() = SwPosition( 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()->nContent == 0 )
1667  {
1668  ++pTmp->GetPoint()->nNode;
1669  pTmp->GetPoint()->nContent.Assign( pTmp->GetContentNode(), 0 );
1670  }
1671  // #i101009#
1672  // prevent redlines that end on structural end node
1673  if (& GetEndOfContent() ==
1674  & pTmp->GetPoint()->nNode.GetNode())
1675  {
1676  --pTmp->GetPoint()->nNode;
1677  SwContentNode *const pContentNode( pTmp->GetContentNode() );
1678  pTmp->GetPoint()->nContent.Assign( pContentNode,
1679  pContentNode ? pContentNode->Len() : 0 );
1680  // tdf#106218 try to avoid losing a paragraph break here:
1681  if (pTmp->GetMark()->nContent == 0)
1682  {
1683  SwNodeIndex const prev(pTmp->GetMark()->nNode, -1);
1684  if (prev.GetNode().IsTextNode())
1685  {
1686  *pTmp->GetMark() = SwPosition(
1687  *prev.GetNode().GetTextNode(),
1688  prev.GetNode().GetTextNode()->Len());
1689  }
1690  }
1691  }
1692 
1693  m_rDoc.getIDocumentRedlineAccess().DeleteRedline( *pTmp, false, RedlineType::Any );
1694 
1695  if (m_rDoc.GetIDocumentUndoRedo().DoesUndo())
1696  {
1698  std::make_unique<SwUndoCompDoc>( *pTmp, false ));
1699  }
1700  m_rDoc.getIDocumentRedlineAccess().AppendRedline( new SwRangeRedline( aRedlnData, *pTmp ), true );
1701 
1702  } while( m_pDelRing.get() != ( pTmp = pTmp->GetNext()) );
1703  }
1704 
1705  pTmp = m_pInsertRing.get();
1706  if( !pTmp )
1707  return;
1708 
1709  do {
1710  if( pTmp->GetPoint()->nContent == 0 )
1711  {
1712  ++pTmp->GetPoint()->nNode;
1713  pTmp->GetPoint()->nContent.Assign( pTmp->GetContentNode(), 0 );
1714  }
1715  // #i101009#
1716  // prevent redlines that end on structural end node
1717  if (& GetEndOfContent() ==
1718  & pTmp->GetPoint()->nNode.GetNode())
1719  {
1720  --pTmp->GetPoint()->nNode;
1721  SwContentNode *const pContentNode( pTmp->GetContentNode() );
1722  pTmp->GetPoint()->nContent.Assign( pContentNode,
1723  pContentNode ? pContentNode->Len() : 0 );
1724  // tdf#106218 try to avoid losing a paragraph break here:
1725  if (pTmp->GetMark()->nContent == 0)
1726  {
1727  SwNodeIndex const prev(pTmp->GetMark()->nNode, -1);
1728  if (prev.GetNode().IsTextNode())
1729  {
1730  *pTmp->GetMark() = SwPosition(
1731  *prev.GetNode().GetTextNode(),
1732  prev.GetNode().GetTextNode()->Len());
1733  }
1734  }
1735  }
1736  } while( m_pInsertRing.get() != ( pTmp = pTmp->GetNext()) );
1737  SwRedlineData aRedlnData( RedlineType::Insert, nAuthor, aTimeStamp,
1738  OUString(), nullptr );
1739 
1740  // combine consecutive
1741  if( pTmp->GetNext() != m_pInsertRing.get() )
1742  {
1743  do {
1744  SwPosition& rSttEnd = *pTmp->End(),
1745  & rEndStt = *pTmp->GetNext()->Start();
1746  const SwContentNode* pCNd;
1747  if( rSttEnd == rEndStt ||
1748  (!rEndStt.nContent.GetIndex() &&
1749  rEndStt.nNode.GetIndex() - 1 == rSttEnd.nNode.GetIndex() &&
1750  nullptr != ( pCNd = rSttEnd.nNode.GetNode().GetContentNode() ) &&
1751  rSttEnd.nContent.GetIndex() == pCNd->Len()))
1752  {
1753  if( pTmp->GetNext() == m_pInsertRing.get() )
1754  {
1755  // are consecutive, so combine
1756  rEndStt = *pTmp->Start();
1757  delete pTmp;
1758  pTmp = m_pInsertRing.get();
1759  }
1760  else
1761  {
1762  // are consecutive, so combine
1763  rSttEnd = *pTmp->GetNext()->End();
1764  delete pTmp->GetNext();
1765  }
1766  }
1767  else
1768  pTmp = pTmp->GetNext();
1769  } while( m_pInsertRing.get() != pTmp );
1770  }
1771 
1772  do {
1775  new SwRangeRedline(aRedlnData, *pTmp), true) &&
1776  m_rDoc.GetIDocumentUndoRedo().DoesUndo())
1777  {
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 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  {
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 
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 
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.nContent.Assign( const_cast<SwContentNode*>(static_cast<const SwContentNode*>(&rDstNd)), pStt->nContent.GetIndex() );
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()->nNode += pEnd->nNode.GetIndex() -
1935  pStt->nNode.GetIndex();
1936  pDestRedl->GetPoint()->nContent.Assign( pDestRedl->GetContentNode(),
1937  pEnd->nContent.GetIndex() );
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()->nNode, -1 );
1951  const sal_Int32 nSaveCnt = pDestRedl->GetPoint()->nContent.GetIndex();
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()->nNode = aSaveNd;
1965  pDestRedl->GetMark()->nContent.Assign( aSaveNd.GetNode().GetContentNode(),
1966  nSaveCnt );
1967 
1968  if( pLastDestRedline && *pLastDestRedline->GetPoint() == *pDestRedl->GetPoint() )
1969  *pLastDestRedline->GetPoint() = *pDestRedl->GetMark();
1970  }
1971  else
1972  {
1973  //JP 21.09.98: Bug 55909
1974  // If there already is a deleted or inserted one at the same position, we have to split it!
1975  SwPosition* pDStt = pDestRedl->GetMark(),
1976  * pDEnd = pDestRedl->GetPoint();
1978 
1979  // find the first redline for StartPos
1980  if( !rDoc.getIDocumentRedlineAccess().GetRedline( *pDStt, &n ) && n )
1981  --n;
1982 
1983  const SwRedlineTable& rRedlineTable = rDoc.getIDocumentRedlineAccess().GetRedlineTable();
1984  for( ; n < rRedlineTable.size(); ++n )
1985  {
1986  SwRangeRedline* pRedl = rRedlineTable[ n ];
1987  SwPosition* pRStt = pRedl->Start(),
1988  * pREnd = pRedl->End();
1989  if( RedlineType::Delete == pRedl->GetType() ||
1990  RedlineType::Insert == pRedl->GetType() )
1991  {
1992  SwComparePosition eCmpPos = ComparePosition( *pDStt, *pDEnd, *pRStt, *pREnd );
1993  switch( eCmpPos )
1994  {
1997  break;
1998 
2001  delete pDestRedl;
2002  pDestRedl = nullptr;
2003  [[fallthrough]];
2004 
2007  n = rRedlineTable.size();
2008  break;
2009 
2011  assert(pDestRedl && "is this actually impossible");
2012  if (pDestRedl)
2013  {
2014  SwRangeRedline* pCpyRedl = new SwRangeRedline(
2015  pDestRedl->GetRedlineData(), *pDStt );
2016  pCpyRedl->SetMark();
2017  *pCpyRedl->GetPoint() = *pRStt;
2018 
2019  std::unique_ptr<SwUndoCompDoc> pUndo;
2020  if (rDoc.GetIDocumentUndoRedo().DoesUndo())
2021  pUndo.reset(new SwUndoCompDoc( *pCpyRedl ));
2022 
2023  // now modify doc: append redline, undo (and count)
2024  rDoc.getIDocumentRedlineAccess().AppendRedline( pCpyRedl, true );
2025  if( pUndo )
2026  {
2027  rDoc.GetIDocumentUndoRedo().AppendUndo(std::move(pUndo));
2028  }
2029  ++nIns;
2030 
2031  *pDStt = *pREnd;
2032 
2033  // we should start over now
2035  }
2036  break;
2037 
2039  *pDEnd = *pRStt;
2040  break;
2041 
2043  *pDStt = *pREnd;
2044  break;
2045  }
2046  }
2047  else if( *pDEnd <= *pRStt )
2048  break;
2049  }
2050 
2051  }
2052 
2053  if( pDestRedl )
2054  {
2055  std::unique_ptr<SwUndoCompDoc> pUndo;
2056  if (rDoc.GetIDocumentUndoRedo().DoesUndo())
2057  pUndo.reset(new SwUndoCompDoc( *pDestRedl ));
2058 
2059  // now modify doc: append redline, undo (and count)
2061  rDoc.getIDocumentRedlineAccess().AppendRedline(pDestRedl, true));
2062  if( pUndo )
2063  {
2064  rDoc.GetIDocumentUndoRedo().AppendUndo( std::move(pUndo) );
2065  }
2066  ++nIns;
2067 
2068  // if AppendRedline has deleted our redline, we may not keep a
2069  // reference to it
2071  pDestRedl = nullptr;
2072  }
2073  return nIns;
2074 }
2075 
2078 {
2079  if( &rDoc == this )
2080  return 0;
2081 
2082  tools::Long nRet = 0;
2083 
2085 
2086  SwDoc& rSrcDoc = const_cast<SwDoc&>(rDoc);
2087  bool bSrcModified = rSrcDoc.getIDocumentState().IsModified();
2088 
2089  RedlineFlags eSrcRedlMode = rSrcDoc.getIDocumentRedlineAccess().GetRedlineFlags();
2092 
2093  CompareMainText aD0(rSrcDoc, false);
2094  CompareMainText aD1(*this, false);
2095  aD1.CompareLines( aD0 );
2096  if( !aD1.HasDiffs( aD0 ) )
2097  {
2098  // we want to get all redlines from the SourceDoc
2099 
2100  // look for all insert redlines from the SourceDoc and determine their position in the DestDoc
2101  std::vector<SaveMergeRedline> vRedlines;
2102  const SwRedlineTable& rSrcRedlTable = rSrcDoc.getIDocumentRedlineAccess().GetRedlineTable();
2103  SwNodeOffset nEndOfExtra = rSrcDoc.GetNodes().GetEndOfExtras().GetIndex();
2104  SwNodeOffset nMyEndOfExtra = GetNodes().GetEndOfExtras().GetIndex();
2105  for(const SwRangeRedline* pRedl : rSrcRedlTable)
2106  {
2107  SwNodeOffset nNd = pRedl->GetPoint()->nNode.GetIndex();
2108  RedlineType eType = pRedl->GetType();
2109  if( nEndOfExtra < nNd &&
2110  ( RedlineType::Insert == eType || RedlineType::Delete == eType ))
2111  {
2112  const SwNode* pDstNd = GetNodes()[
2113  nMyEndOfExtra + nNd - nEndOfExtra ];
2114 
2115  // Found the position.
2116  // Then we also have to insert the redline to the line in the DestDoc.
2117  vRedlines.emplace_back(*pDstNd, *pRedl);
2118  }
2119  }
2120 
2121  if( !vRedlines.empty() )
2122  {
2123  // Carry over all into DestDoc
2125 
2130 
2131  SwPaM* pLastDestRedline(nullptr);
2132  for(SaveMergeRedline& rRedline: vRedlines)
2133  {
2134  nRet += rRedline.InsertRedline(pLastDestRedline);
2135  pLastDestRedline = rRedline.pDestRedl;
2136  }
2137  }
2138  }
2139 
2140  rSrcDoc.getIDocumentRedlineAccess().SetRedlineFlags( eSrcRedlMode );
2141  if( !bSrcModified )
2142  rSrcDoc.getIDocumentState().ResetModified();
2143 
2145 
2147 
2148  return nRet;
2149 }
2150 
2151 LineArrayComparator::LineArrayComparator( const CompareData &rD1,
2152  const CompareData &rD2, int nStt1,
2153  int nEnd1, int nStt2, int nEnd2 )
2154  : m_rData1( rD1 ), m_rData2( rD2 ), m_nFirst1( nStt1 ), m_nFirst2( nStt2 )
2155 {
2156  m_nLen1 = nEnd1 - nStt1;
2157  m_nLen2 = nEnd2 - nStt2;
2158 }
2159 
2160 bool LineArrayComparator::Compare( int nIdx1, int nIdx2 ) const
2161 {
2162  if( nIdx1 < 0 || nIdx2 < 0 || nIdx1 >= m_nLen1 || nIdx2 >= m_nLen2 )
2163  {
2164  OSL_ENSURE( false, "Index out of range!" );
2165  return false;
2166  }
2167 
2168  const SwTextNode *pTextNd1 = m_rData1.GetLine( m_nFirst1 + nIdx1 ).GetNode().GetTextNode();
2169  const SwTextNode *pTextNd2 = m_rData2.GetLine( m_nFirst2 + nIdx2 ).GetNode().GetTextNode();
2170 
2171  if( !pTextNd1 || !pTextNd2
2172  || ( CmpOptions.bUseRsid && !pTextNd1->CompareParRsid( *pTextNd2 ) ) )
2173  {
2174  return false;
2175  }
2176 
2177  const sal_Int32 nPar1Len = pTextNd1->Len();
2178  const sal_Int32 nPar2Len = pTextNd2->Len();
2179 
2180  if( std::min( nPar1Len, nPar2Len ) * 3 < std::max( nPar1Len, nPar2Len ) )
2181  {
2182  return false;
2183  }
2184 
2185  sal_Int32 nBorderLen = ( nPar1Len + nPar2Len )/16;
2186 
2187  if( nBorderLen < 3 )
2188  {
2189  nBorderLen = std::min<sal_Int32>( 3, std::min( nPar1Len, nPar2Len ) );
2190  }
2191 
2192  std::set<unsigned> aHashes;
2193  unsigned nHash = 0;
2194  unsigned nMul = 251;
2195  unsigned nPow = 1;
2196  sal_Int32 i;
2197 
2198  for( i = 0; i < nBorderLen - 1; i++ )
2199  {
2200  nPow *= nMul;
2201  }
2202  for( i = 0; i < nBorderLen; i++ )
2203  {
2204  nHash = nHash*nMul + pTextNd1->GetText()[i];
2205  }
2206  aHashes.insert( nHash );
2207  for( ; i < nPar1Len; i++ )
2208  {
2209  nHash = nHash - nPow*pTextNd1->GetText()[ i - nBorderLen ];
2210  nHash = nHash*nMul + pTextNd1->GetText()[ i ];
2211 
2212  aHashes.insert( nHash );
2213  }
2214 
2215  nHash = 0;
2216  for( i = 0; i < nBorderLen; i++ )
2217  {
2218  nHash = nHash*nMul + pTextNd2->GetText()[ i ];
2219  }
2220 
2221  if( aHashes.find( nHash ) != aHashes.end() )
2222  {
2223  return true;
2224  }
2225 
2226  for( ; i < nPar2Len; i++ )
2227  {
2228  nHash = nHash - nPow*pTextNd2->GetText()[ i - nBorderLen ];
2229  nHash = nHash*nMul + pTextNd2->GetText()[ i ];
2230  if( aHashes.find( nHash ) != aHashes.end() )
2231  {
2232  return true;
2233  }
2234  }
2235  return false;
2236 }
2237 
2238 bool CharArrayComparator::Compare( int nIdx1, int nIdx2 ) const
2239 {
2240  if( nIdx1 < 0 || nIdx2 < 0 || nIdx1 >= GetLen1() || nIdx2 >= GetLen2() )
2241  {
2242  OSL_ENSURE( false, "Index out of range!" );
2243  return false;
2244  }
2245 
2246  return ( !CmpOptions.bUseRsid
2247  || m_pTextNode1->CompareRsid( *m_pTextNode2, nIdx1 + 1, nIdx2 + 1 ) )
2248  && m_pTextNode1->GetText()[ nIdx1 ] == m_pTextNode2->GetText()[ nIdx2 ];
2249 }
2250 
2251 WordArrayComparator::WordArrayComparator( const SwTextNode *pNode1,
2252  const SwTextNode *pNode2 )
2253  : m_pTextNode1( pNode1 ), m_pTextNode2( pNode2 )
2254 {
2255  m_pPos1.reset( new int[ m_pTextNode1->GetText().getLength() + 1 ] );
2256  m_pPos2.reset( new int[ m_pTextNode2->GetText().getLength() + 1 ] );
2257 
2258  CalcPositions( m_pPos1.get(), m_pTextNode1, m_nCount1 );
2259  CalcPositions( m_pPos2.get(), m_pTextNode2, m_nCount2 );
2260 }
2261 
2262 bool WordArrayComparator::Compare( int nIdx1, int nIdx2 ) const
2263 {
2264  int nLen = m_pPos1[ nIdx1 + 1 ] - m_pPos1[ nIdx1 ];
2265  if( nLen != m_pPos2[ nIdx2 + 1 ] - m_pPos2[ nIdx2 ] )
2266  {
2267  return false;
2268  }
2269  for( int i = 0; i < nLen; i++)
2270  {
2271  if( m_pTextNode1->GetText()[ m_pPos1[ nIdx1 ] + i ]
2272  != m_pTextNode2->GetText()[ m_pPos2[ nIdx2 ] + i ]
2273  || ( CmpOptions.bUseRsid && !m_pTextNode1->CompareRsid( *m_pTextNode2,
2274  m_pPos1[ nIdx1 ] + i, m_pPos2[ nIdx2 ] + i ) ) )
2275  {
2276  return false;
2277  }
2278  }
2279  return true;
2280 }
2281 
2282 int WordArrayComparator::GetCharSequence( const int *pWordLcs1,
2283  const int *pWordLcs2, int *pSubseq1, int *pSubseq2, int nLcsLen )
2284 {
2285  int nLen = 0;
2286  for( int i = 0; i < nLcsLen; i++ )
2287  {
2288  // Check for hash collisions
2289  if( m_pPos1[ pWordLcs1[i] + 1 ] - m_pPos1[ pWordLcs1[i] ]
2290  != m_pPos2[ pWordLcs2[i] + 1 ] - m_pPos2[ pWordLcs2[i] ] )
2291  {
2292  continue;
2293  }
2294  for( int j = 0; j < m_pPos1[pWordLcs1[i]+1] - m_pPos1[pWordLcs1[i]]; j++)
2295  {
2296  pSubseq1[ nLen ] = m_pPos1[ pWordLcs1[i] ] + j;
2297  pSubseq2[ nLen ] = m_pPos2[ pWordLcs2[i] ] + j;
2298 
2299  if( m_pTextNode1->GetText()[ m_pPos1[ pWordLcs1[i] ] + j ]
2300  != m_pTextNode2->GetText()[ m_pPos2[ pWordLcs2[i] ] + j ] )
2301  {
2302  nLen -= j;
2303  break;
2304  }
2305 
2306  nLen++;
2307  }
2308  }
2309  return nLen;
2310 }
2311 
2312 void WordArrayComparator::CalcPositions( int *pPos, const SwTextNode *pTextNd,
2313  int &nCnt )
2314 {
2315  nCnt = -1;
2316  for (int i = 0; i <= pTextNd->GetText().getLength(); ++i)
2317  {
2318  if (i == 0 || i == pTextNd->GetText().getLength()
2319  || !rtl::isAsciiAlphanumeric( pTextNd->GetText()[ i - 1 ])
2320  || !rtl::isAsciiAlphanumeric( pTextNd->GetText()[ i ]))
2321  { // Begin new word
2322  nCnt++;
2323  pPos[ nCnt ] = i;
2324  }
2325  }
2326 }
2327 
2328 int CommonSubseq::FindLCS( int *pLcs1, int *pLcs2, int nStt1, int nEnd1,
2329  int nStt2, int nEnd2 )
2330 {
2331  int nLen1 = nEnd1 ? nEnd1 - nStt1 : m_rComparator.GetLen1();
2332  int nLen2 = nEnd2 ? nEnd2 - nStt2 : m_rComparator.GetLen2();
2333 
2334  assert( nLen1 >= 0 );
2335  assert( nLen2 >= 0 );
2336 
2337  std::unique_ptr<int*[]> pLcs( new int*[ nLen1 + 1 ] );
2338  pLcs[ 0 ] = m_pData.get();
2339 
2340  for( int i = 1; i < nLen1 + 1; i++ )
2341  pLcs[ i ] = pLcs[ i - 1 ] + nLen2 + 1;
2342 
2343  for( int i = 0; i <= nLen1; i++ )
2344  pLcs[i][0] = 0;
2345 
2346  for( int j = 0; j <= nLen2; j++ )
2347  pLcs[0][j] = 0;
2348 
2349  // Find lcs
2350  for( int i = 1; i <= nLen1; i++ )
2351  {
2352  for( int j = 1; j <= nLen2; j++ )
2353  {
2354  if( m_rComparator.Compare( nStt1 + i - 1, nStt2 + j - 1 ) )
2355  pLcs[i][j] = pLcs[i - 1][j - 1] + 1;
2356  else
2357  pLcs[i][j] = std::max( pLcs[i][j - 1], pLcs[i - 1][j] );
2358  }
2359  }
2360 
2361  int nLcsLen = pLcs[ nLen1 ][ nLen2 ];
2362 
2363  // Recover the lcs in the two sequences
2364  if( pLcs1 && pLcs2 )
2365  {
2366  int nIdx1 = nLen1;
2367  int nIdx2 = nLen2;
2368  int nIdx = nLcsLen - 1;
2369 
2370  while( nIdx1 > 0 && nIdx2 > 0 )
2371  {
2372  if( pLcs[ nIdx1 ][ nIdx2 ] == pLcs[ nIdx1 - 1 ][ nIdx2 ] )
2373  nIdx1--;
2374  else if( pLcs[ nIdx1 ][ nIdx2 ] == pLcs[ nIdx1 ][ nIdx2 - 1 ] )
2375  nIdx2--;
2376  else
2377  {
2378  nIdx1--;
2379  nIdx2--;
2380  pLcs1[ nIdx ] = nIdx1 + nStt1;
2381  pLcs2[ nIdx ] = nIdx2 + nStt2;
2382  nIdx--;
2383  }
2384  }
2385  }
2386 
2387  return nLcsLen;
2388 }
2389 
2390 int CommonSubseq::IgnoreIsolatedPieces( int *pLcs1, int *pLcs2, int nLen1,
2391  int nLen2, int nLcsLen, int nPieceLen )
2392 {
2393  if( !nLcsLen )
2394  {
2395  return 0;
2396  }
2397 
2398  int nNext = 0;
2399 
2400  // Don't ignore text at the beginning of the paragraphs
2401  if( pLcs1[ 0 ] == 0 && pLcs2[ 0 ] == 0 )
2402  {
2403  while( nNext < nLcsLen - 1 && pLcs1[ nNext ] + 1 == pLcs1[ nNext + 1 ]
2404  && pLcs2[ nNext ] + 1 == pLcs2[ nNext + 1 ] )
2405  {
2406  nNext++;
2407  }
2408  nNext++;
2409  }
2410 
2411  int nCnt = 1;
2412 
2413  for( int i = nNext; i < nLcsLen; i++ )
2414  {
2415  if( i != nLcsLen - 1 && pLcs1[ i ] + 1 == pLcs1[ i + 1 ]
2416  && pLcs2[ i ] + 1 == pLcs2[ i + 1 ] )
2417  {
2418  nCnt++;
2419  }
2420  else
2421  {
2422  if( nCnt > nPieceLen
2423  // Don't ignore text at the end of the paragraphs
2424  || ( i == nLcsLen - 1
2425  && pLcs1[i] == nLen1 - 1 && pLcs2[i] == nLen2 - 1 ))
2426  {
2427  for( int j = i + 1 - nCnt; j <= i; j++ )
2428  {
2429  pLcs2[ nNext ] = pLcs2[ j ];
2430  pLcs1[ nNext ] = pLcs1[ j ];
2431  nNext++;
2432  }
2433  }
2434  nCnt = 1;
2435  }
2436  }
2437 
2438  return nNext;
2439 }
2440 
2441 LgstCommonSubseq::LgstCommonSubseq( ArrayComparator &rComparator )
2442  : CommonSubseq( rComparator, CUTOFF )
2443 {
2444  m_pBuff1.reset( new int[ rComparator.GetLen2() + 1 ] );
2445  m_pBuff2.reset( new int[ rComparator.GetLen2() + 1 ] );
2446 
2447  m_pL1.reset( new int[ rComparator.GetLen2() + 1 ] );
2448  m_pL2.reset( new int[ rComparator.GetLen2() + 1 ] );
2449 }
2450 
2451 void LgstCommonSubseq::FindL( int *pL, int nStt1, int nEnd1,
2452  int nStt2, int nEnd2 )
2453 {
2454  int nLen1 = nEnd1 ? nEnd1 - nStt1 : m_rComparator.GetLen1();
2455  int nLen2 = nEnd2 ? nEnd2 - nStt2 : m_rComparator.GetLen2();
2456 
2457  int *currL = m_pBuff1.get();
2458  int *prevL = m_pBuff2.get();
2459 
2460  // Avoid memory corruption
2461  if( nLen2 > m_rComparator.GetLen2() )
2462  {
2463  assert( false );
2464  return;
2465  }
2466 
2467  memset( m_pBuff1.get(), 0, sizeof( m_pBuff1[0] ) * ( nLen2 + 1 ) );
2468  memset( m_pBuff2.get(), 0, sizeof( m_pBuff2[0] ) * ( nLen2 + 1 ) );
2469 
2470  // Find lcs
2471  for( int i = 1; i <= nLen1; i++ )
2472  {
2473  for( int j = 1; j <= nLen2; j++ )
2474  {
2475  if( m_rComparator.Compare( nStt1 + i - 1, nStt2 + j - 1 ) )
2476  currL[j] = prevL[j - 1] + 1;
2477  else
2478  currL[j] = std::max( currL[j - 1], prevL[j] );
2479  }
2480  int *tmp = currL;
2481  currL = prevL;
2482  prevL = tmp;
2483  }
2484  memcpy( pL, prevL, ( nLen2 + 1 ) * sizeof( *prevL ) );
2485 }
2486 
2487 int LgstCommonSubseq::HirschbergLCS( int *pLcs1, int *pLcs2, int nStt1,
2488  int nEnd1, int nStt2, int nEnd2 )
2489 {
2490  static int nLen1;
2491  static int nLen2;
2492  nLen1 = nEnd1 - nStt1;
2493  nLen2 = nEnd2 - nStt2;
2494 
2495  if( ( nLen1 + 1 ) * ( nLen2 + 1 ) <= CUTOFF )
2496  {
2497  if( !nLen1 || !nLen2 )
2498  {
2499  return 0;
2500  }
2501  return FindLCS(pLcs1, pLcs2, nStt1, nEnd1, nStt2, nEnd2);
2502  }
2503 
2504  int nMid = nLen1/2;
2505 
2506  FindL( m_pL1.get(), nStt1, nStt1 + nMid, nStt2, nEnd2 );
2507  FindL( m_pL2.get(), nStt1 + nMid, nEnd1, nStt2, nEnd2 );
2508 
2509  int nMaxPos = 0;
2510  static int nMaxVal;
2511  nMaxVal = -1;
2512 
2513  static int i;
2514  for( i = 0; i <= nLen2; i++ )
2515  {
2516  if( m_pL1[i] + ( m_pL2[nLen2] - m_pL2[i] ) > nMaxVal )
2517  {
2518  nMaxPos = i;
2519  nMaxVal = m_pL1[i]+( m_pL2[nLen2] - m_pL2[i] );
2520  }
2521  }
2522 
2523  int nRet = HirschbergLCS( pLcs1, pLcs2, nStt1, nStt1 + nMid,
2524  nStt2, nStt2 + nMaxPos );
2525  nRet += HirschbergLCS( pLcs1 + nRet, pLcs2 + nRet, nStt1 + nMid, nEnd1,
2526  nStt2 + nMaxPos, nEnd2 );
2527 
2528  return nRet;
2529 }
2530 
2531 int LgstCommonSubseq::Find( int *pSubseq1, int *pSubseq2 )
2532 {
2533  int nStt = 0;
2534  int nCutEnd = 0;
2535  int nEnd1 = m_rComparator.GetLen1();
2536  int nEnd2 = m_rComparator.GetLen2();
2537 
2538  // Check for corresponding lines in the beginning of the sequences
2539  while( nStt < nEnd1 && nStt < nEnd2 && m_rComparator.Compare( nStt, nStt ) )
2540  {
2541  pSubseq1[ nStt ] = nStt;
2542  pSubseq2[ nStt ] = nStt;
2543  nStt++;
2544  }
2545 
2546  pSubseq1 += nStt;
2547  pSubseq2 += nStt;
2548 
2549  // Check for corresponding lines in the end of the sequences
2550  while( nStt < nEnd1 && nStt < nEnd2
2551  && m_rComparator.Compare( nEnd1 - 1, nEnd2 - 1 ) )
2552  {
2553  nCutEnd++;
2554  nEnd1--;
2555  nEnd2--;
2556  }
2557 
2558  int nLen = HirschbergLCS( pSubseq1, pSubseq2, nStt, nEnd1, nStt, nEnd2 );
2559 
2560  for( int i = 0; i < nCutEnd; i++ )
2561  {
2562  pSubseq1[ nLen + i ] = nEnd1 + i;
2563  pSubseq2[ nLen + i ] = nEnd2 + i;
2564  }
2565 
2566  return nStt + nLen + nCutEnd;
2567 }
2568 
2569 int FastCommonSubseq::FindFastCS( int *pSeq1, int *pSeq2, int nStt1,
2570  int nEnd1, int nStt2, int nEnd2 )
2571 {
2572  int nCutBeg = 0;
2573  int nCutEnd = 0;
2574 
2575  // Check for corresponding lines in the beginning of the sequences
2576  while( nStt1 < nEnd1 && nStt2 < nEnd2 && m_rComparator.Compare( nStt1, nStt2 ) )
2577  {
2578  pSeq1[ nCutBeg ] = nStt1++;
2579  pSeq2[ nCutBeg ] = nStt2++;
2580  nCutBeg++;
2581  }
2582 
2583  pSeq1 += nCutBeg;
2584  pSeq2 += nCutBeg;
2585 
2586  // Check for corresponding lines in the end of the sequences
2587  while( nStt1 < nEnd1 && nStt2 < nEnd2
2588  && m_rComparator.Compare( nEnd1 - 1, nEnd2 - 1 ) )
2589  {
2590  nCutEnd++;
2591  nEnd1--;
2592  nEnd2--;
2593  }
2594 
2595  int nLen1 = nEnd1 - nStt1;
2596  int nLen2 = nEnd2 - nStt2;
2597 
2598  // Return if a sequence is empty
2599  if( nLen1 <= 0 || nLen2 <= 0 )
2600  {
2601  for( int i = 0; i < nCutEnd; i++ )
2602  {
2603  pSeq1[ i ] = nEnd1 + i;
2604  pSeq2[ i ] = nEnd2 + i;
2605  }
2606  return nCutBeg + nCutEnd;
2607  }
2608 
2609  // Cut to LCS for small values
2610  if( nLen1 < 3 || nLen2 < 3 || ( nLen1 + 1 ) * ( nLen2 + 1 ) <= CUTOFF )
2611  {
2612  int nLcsLen = FindLCS( pSeq1, pSeq2, nStt1, nEnd1, nStt2, nEnd2);
2613 
2614  for( int i = 0; i < nCutEnd; i++ )
2615  {
2616  pSeq1[ nLcsLen + i ] = nEnd1 + i;
2617  pSeq2[ nLcsLen + i ] = nEnd2 + i;
2618  }
2619  return nCutBeg + nLcsLen + nCutEnd;
2620  }
2621 
2622  int nMid1 = nLen1/2;
2623  int nMid2 = nLen2/2;
2624 
2625  int nRad;
2626  int nPos1 = -1, nPos2 = -1;
2627 
2628  // Find a point of correspondence in the middle of the sequences
2629  for( nRad = 0; nRad*nRad < std::min( nMid1, nMid2 ); nRad++ )
2630  {
2631  // Search to the left and to the right of the middle of the first sequence
2632  for( int i = nMid1 - nRad; i <= nMid1 + nRad; i++ )
2633  {
2634  if( m_rComparator.Compare( nStt1 + i, nStt2 + nMid2 - nRad ) )
2635  {
2636  nPos1 = nStt1 + i;
2637  nPos2 = nStt2 + nMid2 - nRad;
2638  break;
2639  }
2640  if( m_rComparator.Compare( nStt1 + i, nStt2 + nMid2 + nRad ) )
2641  {
2642  nPos1 = nStt1 + i;
2643  nPos2 = nStt2 + nMid2 - nRad;
2644  break;
2645  }
2646  }
2647  // Search to the left and to the right of the middle of the second sequence
2648  for( int i = nMid2 - nRad; i <= nMid2 + nRad; i++ )
2649  {
2650  if( m_rComparator.Compare( nStt2 + nMid2 - nRad, nStt2 + i ) )
2651  {
2652  nPos2 = nStt2 + i;
2653  nPos1 = nStt1 + nMid1 - nRad;
2654  break;
2655  }
2656  if( m_rComparator.Compare( nStt2 + nMid2 - nRad, nStt2 + i ) )
2657  {
2658  nPos2 = nStt2 + i;
2659  nPos1 = nStt1 + nMid1 - nRad;
2660  break;
2661  }
2662  }
2663  }
2664 
2665  // return if no point of correspondence found
2666  if( nPos1 == -1 )
2667  {
2668  for( int i = 0; i < nCutEnd; i++ )
2669  {
2670  pSeq1[ i ] = nEnd1 + i;
2671  pSeq2[ i ] = nEnd2 + i;
2672  }
2673  return nCutBeg + nCutEnd;
2674  }
2675 
2676  // Run the same on the sequences to the left of the correspondence point
2677  int nLen = FindFastCS( pSeq1, pSeq2, nStt1, nPos1, nStt2, nPos2 );
2678 
2679  pSeq1[ nLen ] = nPos1;
2680  pSeq2[ nLen ] = nPos2;
2681 
2682  // Run the same on the sequences to the right of the correspondence point
2683  nLen += FindFastCS( pSeq1 + nLen + 1, pSeq2 + nLen + 1,
2684  nPos1 + 1, nEnd1, nPos2 + 1, nEnd2 ) + 1;
2685 
2686  for( int i = 0; i < nCutEnd; i++ )
2687  {
2688  pSeq1[ nLen + i ] = nEnd1 + i;
2689  pSeq2[ nLen + i ] = nEnd2 + i;
2690  }
2691 
2692  return nLen + nCutBeg + nCutEnd;
2693 }
2694 
2695 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
const SwEndNode * EndOfSectionNode() const
Definition: node.hxx:692
SwNodeOffset min(const SwNodeOffset &a, const SwNodeOffset &b)
Definition: nodeoffset.hxx:35
tools::Long CompareDoc(const SwDoc &rDoc)
Definition: doccomp.cxx:1832
virtual sal_Int32 Len() const
Definition: node.cxx:1243
SwNodeOffset EndOfSectionIndex() const
Definition: node.hxx:687
Marks a position in the document model.
Definition: pam.hxx:36
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:821
SwComparePosition ComparePosition(const T &rStt1, const T &rEnd1, const T &rStt2, const T &rEnd2)
Definition: pam.hxx:78
const OUString & GetText() const
Definition: ndtxt.hxx:218
SwDocShell * GetDocShell()
Definition: doc.hxx:1351
virtual AppendResult AppendRedline(SwRangeRedline *pNewRedl, bool bCallDelete)=0
Append a new redline.
virtual void SetRedlineFlags_intern(RedlineFlags eMode)=0
Set a new redline mode.
sal_uInt32 getRsidRoot() const
Definition: doc.cxx:216
SwNodeIndex nNode
Definition: pam.hxx:38
virtual sal_Int32 Len() const override
Definition: ndtxt.cxx:277
virtual void SetModified()=0
Must be called manually at changes of format.
sal_uIntPtr sal_uLong
long Long
Pos1 is as large as Pos2.
const SwPosition * GetMark() const
Definition: pam.hxx:210
Pos1 completely contained in Pos2.
sal_Int64 n
virtual SwUndoId EndUndo(SwUndoId const eUndoId, SwRewriter const *const pRewriter)=0
Closes undo block.
Definition: doc.hxx:187
SwSectionNode is derived from SwStartNode.
OUString const & GetTypeName() const
Definition: tox.hxx:708
SwNode & GetNode() const
Definition: ndindex.hxx:119
IDocumentUndoRedo & GetIDocumentUndoRedo()
Definition: doc.cxx:144
OUString const & GetLinkFileName() const
Definition: section.cxx:513
float x
const SwFrameFormats * GetSpzFrameFormats() const
Definition: doc.hxx:743
show all inserts
size_type size() const
Definition: docary.hxx:267
const SwSection & GetSection() const
Definition: node.hxx:549
SwContentNode * GetContentNode(bool bPoint=true) const
Definition: pam.hxx:230
Pos1 end touches at Pos2 start.
SwDoc & m_rDoc
Definition: docbm.cxx:1201
FmFilterData * m_pData
SwNodeType GetNodeType() const
Definition: node.hxx:146
SwIndex nContent
Definition: pam.hxx:39
check if target position is in fly anchored at source range
virtual void DoUndo(bool const bDoUndo)=0
Enable/Disable Undo.
bool IsStartNode() const
Definition: node.hxx:634
Pos2 completely contained in Pos1.
std::pair< CompareDataPtr, CompareDataPtr > CompareDataPtrPair
Definition: doccomp.cxx:1785
SwNodeOffset GetIndex() const
Definition: ndindex.hxx:152
Pos1 before Pos2.
RedlineFlags on.
virtual bool DoesUndo() const =0
Is Undo enabled?
double d
SwPaM * GetNext()
Definition: pam.hxx:265
const SwRedlineData & GetRedlineData(sal_uInt16 nPos=0) const
Definition: docredln.cxx:1952
Specific frame formats (frames, DrawObjects).
float y
SwCompareMode
Definition: modcfg.hxx:87
SwNode & GetEndOfContent() const
Regular ContentSection (i.e. the BodyText).
Definition: ndarr.hxx:162
DocumentType eType
virtual std::size_t GetRedlineAuthor()=0
bool IsContentNode() const
Definition: node.hxx:638
PaM is Point and Mark: a selection of the document model.
Definition: pam.hxx:137
virtual void AppendUndo(std::unique_ptr< SwUndo > pUndo)=0
Add new Undo action.
UNDERLYING_TYPE get() const
Style of a layout element.
Definition: frmfmt.hxx:59
virtual SwUndoId StartUndo(SwUndoId const eUndoId, SwRewriter const *const pRewriter)=0
Opens undo block.
#define SW_MOD()
Definition: swmodule.hxx:255
int i
uno_Any a
SwEndNode * GetEndNode()
Definition: node.hxx:593
const SwStartNode * StartOfSectionNode() const
Definition: node.hxx:133
SwDoc & GetDoc()
Definition: node.hxx:213
const SwPosition * GetPoint() const
Definition: pam.hxx:208
Pos1 start touches at Pos2 end.
virtual bool IsModified() const =0
Changes of document?
bool IsProtect() const
Definition: section.cxx:325
std::vector< CompareDataPtrPair > Comparators
Definition: doccomp.cxx:1786
SwIndex & Assign(SwIndexReg *, sal_Int32)
Definition: index.cxx:206
const SwTOXBase * GetTOXBase() const
Definition: section.cxx:585
virtual bool DeleteRedline(const SwPaM &rPam, bool bSaveInUndo, RedlineType nDelType)=0
SwContentNode * GetContentNode()
Definition: node.hxx:625
SwNodeOffset GetIndex() const
Definition: node.hxx:292
vector_type::size_type size_type
Definition: docary.hxx:222
constexpr std::enable_if_t< std::is_signed_v< T >, std::make_unsigned_t< T > > make_unsigned(T value)
bool CompareRsid(const SwTextNode &rTextNode, sal_Int32 nStt1, sal_Int32 nStt2) const
Definition: ndtxt.cxx:5229
IDocumentState const & getIDocumentState() const
Definition: doc.cxx:394
Marks a node in the document model.
Definition: ndindex.hxx:30
bool IsEndNode() const
Definition: node.hxx:642
bool CompareParRsid(const SwTextNode &rTextNode) const
Definition: ndtxt.cxx:5221
SectionType
Definition: section.hxx:44
virtual std::size_t InsertRedlineAuthor(const OUString &rAuthor)=0
const OUString & GetTitle() const
Definition: tox.hxx:702
show all deletes
const SwPosition * Start() const
Definition: pam.hxx:213
const SwNodeIndex * GetContentIdx() const
Definition: fmtcntnt.hxx:46
virtual const SwRangeRedline * GetRedline(const SwPosition &rPos, SwRedlineTable::size_type *pFndPos) const =0
static CmpOptionsContainer CmpOptions
Definition: doccomp.cxx:323
SwPaM * GetPrev()
Definition: pam.hxx:269
ignore Redlines
sal_Int16 m_nCount
SwTextNode is a paragraph in the document model.
Definition: ndtxt.hxx:79
IDocumentRedlineAccess const & getIDocumentRedlineAccess() const
Definition: doc.cxx:335
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) const
add 4th optional parameter indicating, when that a spa...
Definition: ndtxt.cxx:3412
Pos1 overlaps Pos2 at the end.
const SwNodes & GetNodes() const
Definition: ndindex.hxx:156
TOXTypes GetType() const
Definition: tox.hxx:720
virtual void SetRedlineFlags(RedlineFlags eMode)=0
Set a new redline mode.
sal_Int32 GetIndex() const
Definition: index.hxx:91
SwNodes & GetNodes()
Definition: doc.hxx:408
const SwPosition * End() const
Definition: pam.hxx:218
RedlineType GetType(sal_uInt16 nPos=0) const
Definition: docredln.cxx:1929
SwTableNode is derived from SwStartNode.
Sequence< sal_Int8 > aSeq
o3tl::strong_int< sal_Int32, struct Tag_SwNodeOffset > SwNodeOffset
Definition: nodeoffset.hxx:16
const SwFormatContent & GetContent(bool=true) const
Definition: fmtcntnt.hxx:55
static SwNode * GetEndNode(SwOutlineNodes const *pOutlNds, int nOutlineLevel, SwOutlineNodes::size_type *nOutl)
Definition: docglbl.cxx:103
std::shared_ptr< CompareData > CompareDataPtr
Definition: doccomp.cxx:1784
Any result
virtual RedlineFlags GetRedlineFlags() const =0
Query the currently set redline mode.
bool IsTableNode() const
Definition: node.hxx:650
size_t size() const
static void InsertLine(std::vector< SwTableLine * > &rLineArr, SwTableLine *pLine)
Definition: ndtbl1.cxx:168
RedlineType
SwSectionNode * GetSectionNode()
Definition: node.hxx:617
virtual void SetMark()
Unless this is called, the getter method of Mark will return Point.
Definition: pam.cxx:476
Pos1 behind Pos2.
SectionType GetType() const
Definition: section.hxx:169
tools::Long MergeDoc(const SwDoc &rDoc)
Merge two documents.
Definition: doccomp.cxx:2077
virtual const SwRedlineTable & GetRedlineTable() const =0
SwNode & GetEndOfExtras() const
This is the last EndNode of a special section.
Definition: ndarr.hxx:160
static constexpr size_type npos
Definition: docary.hxx:223
Pos1 overlaps Pos2 at the beginning.
SwComparePosition
Definition: pam.hxx:65
SwTextNode * GetTextNode()
Inline methods from Node.hxx.
Definition: ndtxt.hxx:864
virtual void ResetModified()=0
Base class of the Writer document model elements.
Definition: node.hxx:81