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