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