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