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.data(), aTmpLcsSrc.data() );
1300 
1301  if( CmpOptions.nIgnoreLen )
1302  {
1303  nLcsLen = CommonSubseq::IgnoreIsolatedPieces( aTmpLcsDst.data(), aTmpLcsSrc.data(),
1304  aCmp.GetLen1(), aCmp.GetLen2(),
1305  nLcsLen, CmpOptions.nIgnoreLen );
1306  }
1307 
1308  nLcsLen = aCmp.GetCharSequence( aTmpLcsDst.data(), aTmpLcsSrc.data(),
1309  aLcsDst.data(), aLcsSrc.data(), nLcsLen );
1310  }
1311  else
1312  {
1313  CharArrayComparator aCmp( &rDstNd, &rSrcNd );
1314  LgstCommonSubseq aSeq( aCmp );
1315 
1316  nLcsLen = aSeq.Find( aLcsDst.data(), aLcsSrc.data() );
1317 
1318  if( CmpOptions.nIgnoreLen )
1319  {
1320  nLcsLen = CommonSubseq::IgnoreIsolatedPieces( aLcsDst.data(), aLcsSrc.data(), 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( RedlineType::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, RedlineType::Any );
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( RedlineType::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  if (pSrcIdx->GetNodes()[pSrcIdx->GetIndex() + 1]->IsNoTextNode()
1803  || pDestIdx->GetNodes()[pDestIdx->GetIndex() + 1]->IsNoTextNode())
1804  {
1805  continue; // tdf#125660 don't redline GrfNode/OLENode
1806  }
1807  aComparisons.emplace_back(CompareDataPtr(new CompareFrameFormatText(rSrcDoc, *pSrcIdx)),
1808  CompareDataPtr(new CompareFrameFormatText(rDestDoc, *pDestIdx)));
1809  }
1810  }
1811  return aComparisons;
1812  }
1813 }
1814 
1815 // Returns (the difference count?) if something is different
1816 long SwDoc::CompareDoc( const SwDoc& rDoc )
1817 {
1818  if( &rDoc == this )
1819  return 0;
1820 
1821  long nRet = 0;
1822 
1823  // Get comparison options
1824  CmpOptions.eCmpMode = SW_MOD()->GetCompareMode();
1825  if( CmpOptions.eCmpMode == SwCompareMode::Auto )
1826  {
1827  if( getRsidRoot() == rDoc.getRsidRoot() )
1828  {
1829  CmpOptions.eCmpMode = SwCompareMode::ByChar;
1830  CmpOptions.bUseRsid = true;
1831  CmpOptions.nIgnoreLen = 2;
1832  }
1833  else
1834  {
1835  CmpOptions.eCmpMode = SwCompareMode::ByWord;
1836  CmpOptions.bUseRsid = false;
1837  CmpOptions.nIgnoreLen = 3;
1838  }
1839  }
1840  else
1841  {
1842  CmpOptions.bUseRsid = getRsidRoot() == rDoc.getRsidRoot() && SW_MOD()->IsUseRsid();
1843  CmpOptions.nIgnoreLen = SW_MOD()->IsIgnorePieces() ? SW_MOD()->GetPieceLen() : 0;
1844  }
1845 
1846  GetIDocumentUndoRedo().StartUndo(SwUndoId::EMPTY, nullptr);
1847  bool bDocWasModified = getIDocumentState().IsModified();
1848  SwDoc& rSrcDoc = const_cast<SwDoc&>(rDoc);
1849  bool bSrcModified = rSrcDoc.getIDocumentState().IsModified();
1850 
1851  RedlineFlags eSrcRedlMode = rSrcDoc.getIDocumentRedlineAccess().GetRedlineFlags();
1853  getIDocumentRedlineAccess().SetRedlineFlags(RedlineFlags::On | RedlineFlags::ShowInsert);
1854 
1855  Comparators aComparisons(buildComparators(rSrcDoc, *this));
1856 
1857  for (auto& a : aComparisons)
1858  {
1859  CompareData& rD0 = *a.first.get();
1860  CompareData& rD1 = *a.second.get();
1861  rD1.CompareLines( rD0 );
1862  nRet |= rD1.ShowDiffs( rD0 );
1863  }
1864 
1865  if( nRet )
1866  {
1867  getIDocumentRedlineAccess().SetRedlineFlags(RedlineFlags::On |
1869 
1870  for (auto& a : aComparisons)
1871  {
1872  CompareData& rD1 = *a.second.get();
1873  rD1.SetRedlinesToDoc( !bDocWasModified );
1874  }
1875  getIDocumentState().SetModified();
1876  }
1877 
1878  rSrcDoc.getIDocumentRedlineAccess().SetRedlineFlags( eSrcRedlMode );
1879  getIDocumentRedlineAccess().SetRedlineFlags(RedlineFlags::ShowInsert | RedlineFlags::ShowDelete);
1880 
1881  if( !bSrcModified )
1882  rSrcDoc.getIDocumentState().ResetModified();
1883 
1884  GetIDocumentUndoRedo().EndUndo(SwUndoId::EMPTY, nullptr);
1885 
1886  return nRet;
1887 }
1888 
1889 namespace
1890 {
1891  struct SaveMergeRedline
1892  {
1893  const SwRangeRedline* pSrcRedl;
1894  SwRangeRedline* pDestRedl;
1895  SaveMergeRedline( const SwNode& rDstNd, const SwRangeRedline& rSrcRedl);
1896  sal_uInt16 InsertRedline(SwPaM* pLastDestRedline);
1897  };
1898 }
1899 
1900 SaveMergeRedline::SaveMergeRedline( const SwNode& rDstNd,
1901  const SwRangeRedline& rSrcRedl)
1902  : pSrcRedl( &rSrcRedl )
1903 {
1904  SwPosition aPos( rDstNd );
1905 
1906  const SwPosition* pStt = rSrcRedl.Start();
1907  if( rDstNd.IsContentNode() )
1908  aPos.nContent.Assign( const_cast<SwContentNode*>(static_cast<const SwContentNode*>(&rDstNd)), pStt->nContent.GetIndex() );
1909  pDestRedl = new SwRangeRedline( rSrcRedl.GetRedlineData(), aPos );
1910 
1911  if( RedlineType::Delete == pDestRedl->GetType() )
1912  {
1913  // mark the area as deleted
1914  const SwPosition* pEnd = pStt == rSrcRedl.GetPoint()
1915  ? rSrcRedl.GetMark()
1916  : rSrcRedl.GetPoint();
1917 
1918  pDestRedl->SetMark();
1919  pDestRedl->GetPoint()->nNode += pEnd->nNode.GetIndex() -
1920  pStt->nNode.GetIndex();
1921  pDestRedl->GetPoint()->nContent.Assign( pDestRedl->GetContentNode(),
1922  pEnd->nContent.GetIndex() );
1923  }
1924 }
1925 
1926 sal_uInt16 SaveMergeRedline::InsertRedline(SwPaM* pLastDestRedline)
1927 {
1928  sal_uInt16 nIns = 0;
1929  SwDoc* pDoc = pDestRedl->GetDoc();
1930 
1931  if( RedlineType::Insert == pDestRedl->GetType() )
1932  {
1933  // the part was inserted so copy it from the SourceDoc
1934  ::sw::UndoGuard const undoGuard(pDoc->GetIDocumentUndoRedo());
1935 
1936  SwNodeIndex aSaveNd( pDestRedl->GetPoint()->nNode, -1 );
1937  const sal_Int32 nSaveCnt = pDestRedl->GetPoint()->nContent.GetIndex();
1938 
1941 
1942  pSrcRedl->GetDoc()->getIDocumentContentOperations().CopyRange(
1943  *const_cast<SwPaM*>(static_cast<const SwPaM*>(pSrcRedl)),
1944  *pDestRedl->GetPoint(), /*bCopyAll=*/false, /*bCheckPos=*/true );
1945 
1947 
1948  pDestRedl->SetMark();
1949  ++aSaveNd;
1950  pDestRedl->GetMark()->nNode = aSaveNd;
1951  pDestRedl->GetMark()->nContent.Assign( aSaveNd.GetNode().GetContentNode(),
1952  nSaveCnt );
1953 
1954  if( pLastDestRedline && *pLastDestRedline->GetPoint() == *pDestRedl->GetPoint() )
1955  *pLastDestRedline->GetPoint() = *pDestRedl->GetMark();
1956  }
1957  else
1958  {
1959  //JP 21.09.98: Bug 55909
1960  // If there already is a deleted or inserted one at the same position, we have to split it!
1961  SwPosition* pDStt = pDestRedl->GetMark(),
1962  * pDEnd = pDestRedl->GetPoint();
1964 
1965  // find the first redline for StartPos
1966  if( !pDoc->getIDocumentRedlineAccess().GetRedline( *pDStt, &n ) && n )
1967  --n;
1968 
1969  const SwRedlineTable& rRedlineTable = pDoc->getIDocumentRedlineAccess().GetRedlineTable();
1970  for( ; n < rRedlineTable.size(); ++n )
1971  {
1972  SwRangeRedline* pRedl = rRedlineTable[ n ];
1973  SwPosition* pRStt = pRedl->Start(),
1974  * pREnd = pRStt == pRedl->GetPoint() ? pRedl->GetMark()
1975  : pRedl->GetPoint();
1976  if( RedlineType::Delete == pRedl->GetType() ||
1977  RedlineType::Insert == pRedl->GetType() )
1978  {
1979  SwComparePosition eCmpPos = ComparePosition( *pDStt, *pDEnd, *pRStt, *pREnd );
1980  switch( eCmpPos )
1981  {
1984  break;
1985 
1988  delete pDestRedl;
1989  pDestRedl = nullptr;
1990  [[fallthrough]];
1991 
1994  n = rRedlineTable.size();
1995  break;
1996 
1998  assert(pDestRedl && "is this actually impossible");
1999  if (pDestRedl)
2000  {
2001  SwRangeRedline* pCpyRedl = new SwRangeRedline(
2002  pDestRedl->GetRedlineData(), *pDStt );
2003  pCpyRedl->SetMark();
2004  *pCpyRedl->GetPoint() = *pRStt;
2005 
2006  std::unique_ptr<SwUndoCompDoc> pUndo;
2007  if (pDoc->GetIDocumentUndoRedo().DoesUndo())
2008  pUndo.reset(new SwUndoCompDoc( *pCpyRedl ));
2009 
2010  // now modify doc: append redline, undo (and count)
2011  pDoc->getIDocumentRedlineAccess().AppendRedline( pCpyRedl, true );
2012  if( pUndo )
2013  {
2014  pDoc->GetIDocumentUndoRedo().AppendUndo(std::move(pUndo));
2015  }
2016  ++nIns;
2017 
2018  *pDStt = *pREnd;
2019 
2020  // we should start over now
2022  }
2023  break;
2024 
2026  *pDEnd = *pRStt;
2027  break;
2028 
2030  *pDStt = *pREnd;
2031  break;
2032  }
2033  }
2034  else if( *pDEnd <= *pRStt )
2035  break;
2036  }
2037 
2038  }
2039 
2040  if( pDestRedl )
2041  {
2042  std::unique_ptr<SwUndoCompDoc> pUndo;
2043  if (pDoc->GetIDocumentUndoRedo().DoesUndo())
2044  pUndo.reset(new SwUndoCompDoc( *pDestRedl ));
2045 
2046  // now modify doc: append redline, undo (and count)
2048  pDoc->getIDocumentRedlineAccess().AppendRedline(pDestRedl, true));
2049  if( pUndo )
2050  {
2051  pDoc->GetIDocumentUndoRedo().AppendUndo( std::move(pUndo) );
2052  }
2053  ++nIns;
2054 
2055  // if AppendRedline has deleted our redline, we may not keep a
2056  // reference to it
2058  pDestRedl = nullptr;
2059  }
2060  return nIns;
2061 }
2062 
2064 long SwDoc::MergeDoc( const SwDoc& rDoc )
2065 {
2066  if( &rDoc == this )
2067  return 0;
2068 
2069  long nRet = 0;
2070 
2072 
2073  SwDoc& rSrcDoc = const_cast<SwDoc&>(rDoc);
2074  bool bSrcModified = rSrcDoc.getIDocumentState().IsModified();
2075 
2076  RedlineFlags eSrcRedlMode = rSrcDoc.getIDocumentRedlineAccess().GetRedlineFlags();
2079 
2080  CompareMainText aD0(rSrcDoc, false);
2081  CompareMainText aD1(*this, false);
2082  aD1.CompareLines( aD0 );
2083  if( !aD1.HasDiffs( aD0 ) )
2084  {
2085  // we want to get all redlines from the SourceDoc
2086 
2087  // look for all insert redlines from the SourceDoc and determine their position in the DestDoc
2088  std::vector<SaveMergeRedline> vRedlines;
2089  const SwRedlineTable& rSrcRedlTable = rSrcDoc.getIDocumentRedlineAccess().GetRedlineTable();
2090  sal_uLong nEndOfExtra = rSrcDoc.GetNodes().GetEndOfExtras().GetIndex();
2091  sal_uLong nMyEndOfExtra = GetNodes().GetEndOfExtras().GetIndex();
2092  for(const SwRangeRedline* pRedl : rSrcRedlTable)
2093  {
2094  sal_uLong nNd = pRedl->GetPoint()->nNode.GetIndex();
2095  RedlineType eType = pRedl->GetType();
2096  if( nEndOfExtra < nNd &&
2097  ( RedlineType::Insert == eType || RedlineType::Delete == eType ))
2098  {
2099  const SwNode* pDstNd = GetNodes()[
2100  nMyEndOfExtra + nNd - nEndOfExtra ];
2101 
2102  // Found the position.
2103  // Then we also have to insert the redline to the line in the DestDoc.
2104  vRedlines.emplace_back(*pDstNd, *pRedl);
2105  }
2106  }
2107 
2108  if( !vRedlines.empty() )
2109  {
2110  // Carry over all into DestDoc
2112 
2117 
2118  SwPaM* pLastDestRedline(nullptr);
2119  for(SaveMergeRedline& rRedline: vRedlines)
2120  {
2121  nRet += rRedline.InsertRedline(pLastDestRedline);
2122  pLastDestRedline = rRedline.pDestRedl;
2123  }
2124  }
2125  }
2126 
2127  rSrcDoc.getIDocumentRedlineAccess().SetRedlineFlags( eSrcRedlMode );
2128  if( !bSrcModified )
2129  rSrcDoc.getIDocumentState().ResetModified();
2130 
2132 
2134 
2135  return nRet;
2136 }
2137 
2139  const CompareData &rD2, int nStt1,
2140  int nEnd1, int nStt2, int nEnd2 )
2141  : rData1( rD1 ), rData2( rD2 ), nFirst1( nStt1 ), nFirst2( nStt2 )
2142 {
2143  nLen1 = nEnd1 - nStt1;
2144  nLen2 = nEnd2 - nStt2;
2145 }
2146 
2147 bool LineArrayComparator::Compare( int nIdx1, int nIdx2 ) const
2148 {
2149  if( nIdx1 < 0 || nIdx2 < 0 || nIdx1 >= nLen1 || nIdx2 >= nLen2 )
2150  {
2151  OSL_ENSURE( false, "Index out of range!" );
2152  return false;
2153  }
2154 
2155  const SwTextNode *pTextNd1 = rData1.GetLine( nFirst1 + nIdx1 )->GetNode().GetTextNode();
2156  const SwTextNode *pTextNd2 = rData2.GetLine( nFirst2 + nIdx2 )->GetNode().GetTextNode();
2157 
2158  if( !pTextNd1 || !pTextNd2
2159  || ( CmpOptions.bUseRsid && !pTextNd1->CompareParRsid( *pTextNd2 ) ) )
2160  {
2161  return false;
2162  }
2163 
2164  const sal_Int32 nPar1Len = pTextNd1->Len();
2165  const sal_Int32 nPar2Len = pTextNd2->Len();
2166 
2167  if( std::min( nPar1Len, nPar2Len ) * 3 < std::max( nPar1Len, nPar2Len ) )
2168  {
2169  return false;
2170  }
2171 
2172  sal_Int32 nBorderLen = ( nPar1Len + nPar2Len )/16;
2173 
2174  if( nBorderLen < 3 )
2175  {
2176  nBorderLen = std::min<sal_Int32>( 3, std::min( nPar1Len, nPar2Len ) );
2177  }
2178 
2179  std::set<unsigned> aHashes;
2180  unsigned nHash = 0;
2181  unsigned nMul = 251;
2182  unsigned nPow = 1;
2183  sal_Int32 i;
2184 
2185  for( i = 0; i < nBorderLen - 1; i++ )
2186  {
2187  nPow *= nMul;
2188  }
2189  for( i = 0; i < nBorderLen; i++ )
2190  {
2191  nHash = nHash*nMul + pTextNd1->GetText()[i];
2192  }
2193  aHashes.insert( nHash );
2194  for( ; i < nPar1Len; i++ )
2195  {
2196  nHash = nHash - nPow*pTextNd1->GetText()[ i - nBorderLen ];
2197  nHash = nHash*nMul + pTextNd1->GetText()[ i ];
2198 
2199  aHashes.insert( nHash );
2200  }
2201 
2202  nHash = 0;
2203  for( i = 0; i < nBorderLen; i++ )
2204  {
2205  nHash = nHash*nMul + pTextNd2->GetText()[ i ];
2206  }
2207 
2208  if( aHashes.find( nHash ) != aHashes.end() )
2209  {
2210  return true;
2211  }
2212 
2213  for( ; i < nPar2Len; i++ )
2214  {
2215  nHash = nHash - nPow*pTextNd2->GetText()[ i - nBorderLen ];
2216  nHash = nHash*nMul + pTextNd2->GetText()[ i ];
2217  if( aHashes.find( nHash ) != aHashes.end() )
2218  {
2219  return true;
2220  }
2221  }
2222  return false;
2223 }
2224 
2225 bool CharArrayComparator::Compare( int nIdx1, int nIdx2 ) const
2226 {
2227  if( nIdx1 < 0 || nIdx2 < 0 || nIdx1 >= GetLen1() || nIdx2 >= GetLen2() )
2228  {
2229  OSL_ENSURE( false, "Index out of range!" );
2230  return false;
2231  }
2232 
2233  return ( !CmpOptions.bUseRsid
2234  || pTextNd1->CompareRsid( *pTextNd2, nIdx1 + 1, nIdx2 + 1 ) )
2235  && pTextNd1->GetText()[ nIdx1 ] == pTextNd2->GetText()[ nIdx2 ];
2236 }
2237 
2239  const SwTextNode *pNode2 )
2240  : pTextNd1( pNode1 ), pTextNd2( pNode2 )
2241 {
2242  pPos1.reset( new int[ pTextNd1->GetText().getLength() + 1 ] );
2243  pPos2.reset( new int[ pTextNd2->GetText().getLength() + 1 ] );
2244 
2245  CalcPositions( pPos1.get(), pTextNd1, nCnt1 );
2246  CalcPositions( pPos2.get(), pTextNd2, nCnt2 );
2247 }
2248 
2249 bool WordArrayComparator::Compare( int nIdx1, int nIdx2 ) const
2250 {
2251  int nLen = pPos1[ nIdx1 + 1 ] - pPos1[ nIdx1 ];
2252  if( nLen != pPos2[ nIdx2 + 1 ] - pPos2[ nIdx2 ] )
2253  {
2254  return false;
2255  }
2256  for( int i = 0; i < nLen; i++)
2257  {
2258  if( pTextNd1->GetText()[ pPos1[ nIdx1 ] + i ]
2259  != pTextNd2->GetText()[ pPos2[ nIdx2 ] + i ]
2260  || ( CmpOptions.bUseRsid && !pTextNd1->CompareRsid( *pTextNd2,
2261  pPos1[ nIdx1 ] + i, pPos2[ nIdx2 ] + i ) ) )
2262  {
2263  return false;
2264  }
2265  }
2266  return true;
2267 }
2268 
2269 int WordArrayComparator::GetCharSequence( const int *pWordLcs1,
2270  const int *pWordLcs2, int *pSubseq1, int *pSubseq2, int nLcsLen )
2271 {
2272  int nLen = 0;
2273  for( int i = 0; i < nLcsLen; i++ )
2274  {
2275  // Check for hash collisions
2276  if( pPos1[ pWordLcs1[i] + 1 ] - pPos1[ pWordLcs1[i] ]
2277  != pPos2[ pWordLcs2[i] + 1 ] - pPos2[ pWordLcs2[i] ] )
2278  {
2279  continue;
2280  }
2281  for( int j = 0; j < pPos1[pWordLcs1[i]+1] - pPos1[pWordLcs1[i]]; j++)
2282  {
2283  pSubseq1[ nLen ] = pPos1[ pWordLcs1[i] ] + j;
2284  pSubseq2[ nLen ] = pPos2[ pWordLcs2[i] ] + j;
2285 
2286  if( pTextNd1->GetText()[ pPos1[ pWordLcs1[i] ] + j ]
2287  != pTextNd2->GetText()[ pPos2[ pWordLcs2[i] ] + j ] )
2288  {
2289  nLen -= j;
2290  break;
2291  }
2292 
2293  nLen++;
2294  }
2295  }
2296  return nLen;
2297 }
2298 
2299 void WordArrayComparator::CalcPositions( int *pPos, const SwTextNode *pTextNd,
2300  int &nCnt )
2301 {
2302  nCnt = -1;
2303  for (int i = 0; i <= pTextNd->GetText().getLength(); ++i)
2304  {
2305  if (i == 0 || i == pTextNd->GetText().getLength()
2306  || !rtl::isAsciiAlphanumeric( pTextNd->GetText()[ i - 1 ])
2307  || !rtl::isAsciiAlphanumeric( pTextNd->GetText()[ i ]))
2308  { // Begin new word
2309  nCnt++;
2310  pPos[ nCnt ] = i;
2311  }
2312  }
2313 }
2314 
2315 int CommonSubseq::FindLCS( int *pLcs1, int *pLcs2, int nStt1, int nEnd1,
2316  int nStt2, int nEnd2 )
2317 {
2318  int nLen1 = nEnd1 ? nEnd1 - nStt1 : rCmp.GetLen1();
2319  int nLen2 = nEnd2 ? nEnd2 - nStt2 : rCmp.GetLen2();
2320 
2321  assert( nLen1 >= 0 );
2322  assert( nLen2 >= 0 );
2323 
2324  std::unique_ptr<int*[]> pLcs( new int*[ nLen1 + 1 ] );
2325  pLcs[ 0 ] = pData.get();
2326 
2327  for( int i = 1; i < nLen1 + 1; i++ )
2328  pLcs[ i ] = pLcs[ i - 1 ] + nLen2 + 1;
2329 
2330  for( int i = 0; i <= nLen1; i++ )
2331  pLcs[i][0] = 0;
2332 
2333  for( int j = 0; j <= nLen2; j++ )
2334  pLcs[0][j] = 0;
2335 
2336  // Find lcs
2337  for( int i = 1; i <= nLen1; i++ )
2338  {
2339  for( int j = 1; j <= nLen2; j++ )
2340  {
2341  if( rCmp.Compare( nStt1 + i - 1, nStt2 + j - 1 ) )
2342  pLcs[i][j] = pLcs[i - 1][j - 1] + 1;
2343  else
2344  pLcs[i][j] = std::max( pLcs[i][j - 1], pLcs[i - 1][j] );
2345  }
2346  }
2347 
2348  int nLcsLen = pLcs[ nLen1 ][ nLen2 ];
2349 
2350  // Recover the lcs in the two sequences
2351  if( pLcs1 && pLcs2 )
2352  {
2353  int nIdx1 = nLen1;
2354  int nIdx2 = nLen2;
2355  int nIdx = nLcsLen - 1;
2356 
2357  while( nIdx1 > 0 && nIdx2 > 0 )
2358  {
2359  if( pLcs[ nIdx1 ][ nIdx2 ] == pLcs[ nIdx1 - 1 ][ nIdx2 ] )
2360  nIdx1--;
2361  else if( pLcs[ nIdx1 ][ nIdx2 ] == pLcs[ nIdx1 ][ nIdx2 - 1 ] )
2362  nIdx2--;
2363  else
2364  {
2365  nIdx1--;
2366  nIdx2--;
2367  pLcs1[ nIdx ] = nIdx1 + nStt1;
2368  pLcs2[ nIdx ] = nIdx2 + nStt2;
2369  nIdx--;
2370  }
2371  }
2372  }
2373 
2374  return nLcsLen;
2375 }
2376 
2377 int CommonSubseq::IgnoreIsolatedPieces( int *pLcs1, int *pLcs2, int nLen1,
2378  int nLen2, int nLcsLen, int nPieceLen )
2379 {
2380  if( !nLcsLen )
2381  {
2382  return 0;
2383  }
2384 
2385  int nNext = 0;
2386 
2387  // Don't ignore text at the beginning of the paragraphs
2388  if( pLcs1[ 0 ] == 0 && pLcs2[ 0 ] == 0 )
2389  {
2390  while( nNext < nLcsLen - 1 && pLcs1[ nNext ] + 1 == pLcs1[ nNext + 1 ]
2391  && pLcs2[ nNext ] + 1 == pLcs2[ nNext + 1 ] )
2392  {
2393  nNext++;
2394  }
2395  nNext++;
2396  }
2397 
2398  int nCnt = 1;
2399 
2400  for( int i = nNext; i < nLcsLen; i++ )
2401  {
2402  if( i != nLcsLen - 1 && pLcs1[ i ] + 1 == pLcs1[ i + 1 ]
2403  && pLcs2[ i ] + 1 == pLcs2[ i + 1 ] )
2404  {
2405  nCnt++;
2406  }
2407  else
2408  {
2409  if( nCnt > nPieceLen
2410  // Don't ignore text at the end of the paragraphs
2411  || ( i == nLcsLen - 1
2412  && pLcs1[i] == nLen1 - 1 && pLcs2[i] == nLen2 - 1 ))
2413  {
2414  for( int j = i + 1 - nCnt; j <= i; j++ )
2415  {
2416  pLcs2[ nNext ] = pLcs2[ j ];
2417  pLcs1[ nNext ] = pLcs1[ j ];
2418  nNext++;
2419  }
2420  }
2421  nCnt = 1;
2422  }
2423  }
2424 
2425  return nNext;
2426 }
2427 
2429  : CommonSubseq( rComparator, CUTOFF )
2430 {
2431  pBuff1.reset( new int[ rComparator.GetLen2() + 1 ] );
2432  pBuff2.reset( new int[ rComparator.GetLen2() + 1 ] );
2433 
2434  pL1.reset( new int[ rComparator.GetLen2() + 1 ] );
2435  pL2.reset( new int[ rComparator.GetLen2() + 1 ] );
2436 }
2437 
2438 void LgstCommonSubseq::FindL( int *pL, int nStt1, int nEnd1,
2439  int nStt2, int nEnd2 )
2440 {
2441  int nLen1 = nEnd1 ? nEnd1 - nStt1 : rCmp.GetLen1();
2442  int nLen2 = nEnd2 ? nEnd2 - nStt2 : rCmp.GetLen2();
2443 
2444  int *currL = pBuff1.get();
2445  int *prevL = pBuff2.get();
2446 
2447  // Avoid memory corruption
2448  if( nLen2 > rCmp.GetLen2() )
2449  {
2450  assert( false );
2451  return;
2452  }
2453 
2454  memset( pBuff1.get(), 0, sizeof( *pBuff1.get() ) * ( nLen2 + 1 ) );
2455  memset( pBuff2.get(), 0, sizeof( *pBuff2.get() ) * ( nLen2 + 1 ) );
2456 
2457  // Find lcs
2458  for( int i = 1; i <= nLen1; i++ )
2459  {
2460  for( int j = 1; j <= nLen2; j++ )
2461  {
2462  if( rCmp.Compare( nStt1 + i - 1, nStt2 + j - 1 ) )
2463  currL[j] = prevL[j - 1] + 1;
2464  else
2465  currL[j] = std::max( currL[j - 1], prevL[j] );
2466  }
2467  int *tmp = currL;
2468  currL = prevL;
2469  prevL = tmp;
2470  }
2471  memcpy( pL, prevL, ( nLen2 + 1 ) * sizeof( *prevL ) );
2472 }
2473 
2474 int LgstCommonSubseq::HirschbergLCS( int *pLcs1, int *pLcs2, int nStt1,
2475  int nEnd1, int nStt2, int nEnd2 )
2476 {
2477  static int nLen1;
2478  static int nLen2;
2479  nLen1 = nEnd1 - nStt1;
2480  nLen2 = nEnd2 - nStt2;
2481 
2482  if( ( nLen1 + 1 ) * ( nLen2 + 1 ) <= CUTOFF )
2483  {
2484  if( !nLen1 || !nLen2 )
2485  {
2486  return 0;
2487  }
2488  return FindLCS(pLcs1, pLcs2, nStt1, nEnd1, nStt2, nEnd2);
2489  }
2490 
2491  int nMid = nLen1/2;
2492 
2493  FindL( pL1.get(), nStt1, nStt1 + nMid, nStt2, nEnd2 );
2494  FindL( pL2.get(), nStt1 + nMid, nEnd1, nStt2, nEnd2 );
2495 
2496  int nMaxPos = 0;
2497  static int nMaxVal;
2498  nMaxVal = -1;
2499 
2500  static int i;
2501  for( i = 0; i <= nLen2; i++ )
2502  {
2503  if( pL1[i] + ( pL2[nLen2] - pL2[i] ) > nMaxVal )
2504  {
2505  nMaxPos = i;
2506  nMaxVal = pL1[i]+( pL2[nLen2] - pL2[i] );
2507  }
2508  }
2509 
2510  int nRet = HirschbergLCS( pLcs1, pLcs2, nStt1, nStt1 + nMid,
2511  nStt2, nStt2 + nMaxPos );
2512  nRet += HirschbergLCS( pLcs1 + nRet, pLcs2 + nRet, nStt1 + nMid, nEnd1,
2513  nStt2 + nMaxPos, nEnd2 );
2514 
2515  return nRet;
2516 }
2517 
2518 int LgstCommonSubseq::Find( int *pSubseq1, int *pSubseq2 )
2519 {
2520  int nStt = 0;
2521  int nCutEnd = 0;
2522  int nEnd1 = rCmp.GetLen1();
2523  int nEnd2 = rCmp.GetLen2();
2524 
2525  // Check for corresponding lines in the beginning of the sequences
2526  while( nStt < nEnd1 && nStt < nEnd2 && rCmp.Compare( nStt, nStt ) )
2527  {
2528  pSubseq1[ nStt ] = nStt;
2529  pSubseq2[ nStt ] = nStt;
2530  nStt++;
2531  }
2532 
2533  pSubseq1 += nStt;
2534  pSubseq2 += nStt;
2535 
2536  // Check for corresponding lines in the end of the sequences
2537  while( nStt < nEnd1 && nStt < nEnd2
2538  && rCmp.Compare( nEnd1 - 1, nEnd2 - 1 ) )
2539  {
2540  nCutEnd++;
2541  nEnd1--;
2542  nEnd2--;
2543  }
2544 
2545  int nLen = HirschbergLCS( pSubseq1, pSubseq2, nStt, nEnd1, nStt, nEnd2 );
2546 
2547  for( int i = 0; i < nCutEnd; i++ )
2548  {
2549  pSubseq1[ nLen + i ] = nEnd1 + i;
2550  pSubseq2[ nLen + i ] = nEnd2 + i;
2551  }
2552 
2553  return nStt + nLen + nCutEnd;
2554 }
2555 
2556 int FastCommonSubseq::FindFastCS( int *pSeq1, int *pSeq2, int nStt1,
2557  int nEnd1, int nStt2, int nEnd2 )
2558 {
2559  int nCutBeg = 0;
2560  int nCutEnd = 0;
2561 
2562  // Check for corresponding lines in the beginning of the sequences
2563  while( nStt1 < nEnd1 && nStt2 < nEnd2 && rCmp.Compare( nStt1, nStt2 ) )
2564  {
2565  pSeq1[ nCutBeg ] = nStt1++;
2566  pSeq2[ nCutBeg ] = nStt2++;
2567  nCutBeg++;
2568  }
2569 
2570  pSeq1 += nCutBeg;
2571  pSeq2 += nCutBeg;
2572 
2573  // Check for corresponding lines in the end of the sequences
2574  while( nStt1 < nEnd1 && nStt2 < nEnd2
2575  && rCmp.Compare( nEnd1 - 1, nEnd2 - 1 ) )
2576  {
2577  nCutEnd++;
2578  nEnd1--;
2579  nEnd2--;
2580  }
2581 
2582  int nLen1 = nEnd1 - nStt1;
2583  int nLen2 = nEnd2 - nStt2;
2584 
2585  // Return if a sequence is empty
2586  if( nLen1 <= 0 || nLen2 <= 0 )
2587  {
2588  for( int i = 0; i < nCutEnd; i++ )
2589  {
2590  pSeq1[ i ] = nEnd1 + i;
2591  pSeq2[ i ] = nEnd2 + i;
2592  }
2593  return nCutBeg + nCutEnd;
2594  }
2595 
2596  // Cut to LCS for small values
2597  if( nLen1 < 3 || nLen2 < 3 || ( nLen1 + 1 ) * ( nLen2 + 1 ) <= CUTOFF )
2598  {
2599  int nLcsLen = FindLCS( pSeq1, pSeq2, nStt1, nEnd1, nStt2, nEnd2);
2600 
2601  for( int i = 0; i < nCutEnd; i++ )
2602  {
2603  pSeq1[ nLcsLen + i ] = nEnd1 + i;
2604  pSeq2[ nLcsLen + i ] = nEnd2 + i;
2605  }
2606  return nCutBeg + nLcsLen + nCutEnd;
2607  }
2608 
2609  int nMid1 = nLen1/2;
2610  int nMid2 = nLen2/2;
2611 
2612  int nRad;
2613  int nPos1 = -1, nPos2 = -1;
2614 
2615  // Find a point of correspondence in the middle of the sequences
2616  for( nRad = 0; nRad*nRad < std::min( nMid1, nMid2 ); nRad++ )
2617  {
2618  // Search to the left and to the right of the middle of the first sequence
2619  for( int i = nMid1 - nRad; i <= nMid1 + nRad; i++ )
2620  {
2621  if( rCmp.Compare( nStt1 + i, nStt2 + nMid2 - nRad ) )
2622  {
2623  nPos1 = nStt1 + i;
2624  nPos2 = nStt2 + nMid2 - nRad;
2625  break;
2626  }
2627  if( rCmp.Compare( nStt1 + i, nStt2 + nMid2 + nRad ) )
2628  {
2629  nPos1 = nStt1 + i;
2630  nPos2 = nStt2 + nMid2 - nRad;
2631  break;
2632  }
2633  }
2634  // Search to the left and to the right of the middle of the second sequence
2635  for( int i = nMid2 - nRad; i <= nMid2 + nRad; i++ )
2636  {
2637  if( rCmp.Compare( nStt2 + nMid2 - nRad, nStt2 + i ) )
2638  {
2639  nPos2 = nStt2 + i;
2640  nPos1 = nStt1 + nMid1 - nRad;
2641  break;
2642  }
2643  if( rCmp.Compare( nStt2 + nMid2 - nRad, nStt2 + i ) )
2644  {
2645  nPos2 = nStt2 + i;
2646  nPos1 = nStt1 + nMid1 - nRad;
2647  break;
2648  }
2649  }
2650  }
2651 
2652  // return if no point of correspondence found
2653  if( nPos1 == -1 )
2654  {
2655  for( int i = 0; i < nCutEnd; i++ )
2656  {
2657  pSeq1[ i ] = nEnd1 + i;
2658  pSeq2[ i ] = nEnd2 + i;
2659  }
2660  return nCutBeg + nCutEnd;
2661  }
2662 
2663  // Run the same on the sequences to the left of the correspondence point
2664  int nLen = FindFastCS( pSeq1, pSeq2, nStt1, nPos1, nStt2, nPos2 );
2665 
2666  pSeq1[ nLen ] = nPos1;
2667  pSeq2[ nLen ] = nPos2;
2668 
2669  // Run the same on the sequences to the right of the correspondence point
2670  nLen += FindFastCS( pSeq1 + nLen + 1, pSeq2 + nLen + 1,
2671  nPos1 + 1, nEnd1, nPos2 + 1, nEnd2 ) + 1;
2672 
2673  for( int i = 0; i < nCutEnd; i++ )
2674  {
2675  pSeq1[ nLen + i ] = nEnd1 + i;
2676  pSeq2[ nLen + i ] = nEnd2 + i;
2677  }
2678 
2679  return nLen + nCutBeg + nCutEnd;
2680 }
2681 
2682 /* 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:1816
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:2556
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:2518
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:2377
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:368
int GetCharSequence(const int *pWordLcs1, const int *pWordLcs2, int *pSubseq1, int *pSubseq2, int nLcsLen)
Definition: doccomp.cxx:2269
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:2438
Pos1 end touches at Pos2 start.
int HirschbergLCS(int *pLcs1, int *pLcs2, int nStt1, int nEnd1, int nStt2, int nEnd2)
Definition: doccomp.cxx:2474
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:2238
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:2315
std::pair< CompareDataPtr, CompareDataPtr > CompareDataPtrPair
Definition: doccomp.cxx:1769
Pos1 before Pos2.
RedlineFlags on.
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:1731
Specific frame formats (frames, DrawObjects).
Definition: docary.hxx:201
float y
SwCompareMode
Definition: modcfg.hxx:87
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.
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:330
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:2147
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:2064
const CompareData & rData1
Definition: doccomp.cxx:263
bool CompareRsid(const SwTextNode &rTextNode, sal_Int32 nStt1, sal_Int32 nStt2) const
Definition: ndtxt.cxx:5230
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:5222
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:2138
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
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:3382
Pos1 overlaps Pos2 at the end.
const SwNodes & GetNodes() const
Definition: ndindex.hxx:155
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
static const int CUTOFF
Definition: doccomp.cxx:345
LgstCommonSubseq(ArrayComparator &rComparator)
Definition: doccomp.cxx:2428
virtual void SetRedlineFlags(RedlineFlags eMode)=0
Set a new redline mode.
static void CalcPositions(int *pPos, const SwTextNode *pTextNd, int &nCnt)
Definition: doccomp.cxx:2299
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
RedlineType GetType(sal_uInt16 nPos=0) const
Definition: docredln.cxx:1713
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:2225
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:225
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:2249
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: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:843
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.