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