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