Bug Summary

File:home/maarten/src/libreoffice/core/sw/source/core/doc/doccomp.cxx
Warning:line 1509, column 1
Potential leak of memory pointed to by 'pTmp'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name doccomp.cxx -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -mframe-pointer=all -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -fno-split-dwarf-inlining -debugger-tuning=gdb -resource-dir /usr/lib64/clang/11.0.0 -isystem /usr/include/libxml2 -D BOOST_ERROR_CODE_HEADER_ONLY -D BOOST_SYSTEM_NO_DEPRECATED -D CPPU_ENV=gcc3 -D LINUX -D OSL_DEBUG_LEVEL=1 -D SAL_LOG_INFO -D SAL_LOG_WARN -D UNIX -D UNX -D X86_64 -D _PTHREADS -D _REENTRANT -D SW_DLLIMPLEMENTATION -D SWUI_DLL_NAME="libswuilo.so" -D SYSTEM_LIBXML -D EXCEPTIONS_ON -D LIBO_INTERNAL_ONLY -I /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/icu/source -I /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/icu/source/i18n -I /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/icu/source/common -I /home/maarten/src/libreoffice/core/external/boost/include -I /home/maarten/src/libreoffice/core/workdir/UnpackedTarball/boost -I /home/maarten/src/libreoffice/core/sw/source/core/inc -I /home/maarten/src/libreoffice/core/sw/source/filter/inc -I /home/maarten/src/libreoffice/core/sw/source/uibase/inc -I /home/maarten/src/libreoffice/core/sw/inc -I /home/maarten/src/libreoffice/core/workdir/SdiTarget/sw/sdi -I /home/maarten/src/libreoffice/core/include -I /usr/lib/jvm/java-11-openjdk-11.0.9.10-0.0.ea.fc33.x86_64/include -I /usr/lib/jvm/java-11-openjdk-11.0.9.10-0.0.ea.fc33.x86_64/include/linux -I /home/maarten/src/libreoffice/core/config_host -I /home/maarten/src/libreoffice/core/workdir/CustomTarget/officecfg/registry -I /home/maarten/src/libreoffice/core/workdir/CustomTarget/sw/generated -I /home/maarten/src/libreoffice/core/workdir/UnoApiHeadersTarget/udkapi/normal -I /home/maarten/src/libreoffice/core/workdir/UnoApiHeadersTarget/offapi/normal -I /home/maarten/src/libreoffice/core/workdir/UnoApiHeadersTarget/oovbaapi/normal -internal-isystem /usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10 -internal-isystem /usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10/x86_64-redhat-linux -internal-isystem /usr/bin/../lib/gcc/x86_64-redhat-linux/10/../../../../include/c++/10/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib64/clang/11.0.0/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O0 -Wno-missing-braces -std=c++17 -fdeprecated-macro -fdebug-compilation-dir /home/maarten/src/libreoffice/core -ferror-limit 19 -fvisibility hidden -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcxx-exceptions -fexceptions -debug-info-kind=constructor -analyzer-output=html -faddrsig -o /home/maarten/tmp/wis/scan-build-libreoffice/output/report/2020-10-07-141433-9725-1 -x c++ /home/maarten/src/libreoffice/core/sw/source/core/doc/doccomp.cxx
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>
29#include <DocumentContentOperationsManager.hxx>
30#include <IDocumentRedlineAccess.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
52using namespace ::com::sun::star;
53
54using std::vector;
55
56namespace {
57
58class SwCompareLine
59{
60 const SwNode& m_rNode;
61public:
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
84class CompareData
85{
86protected:
87 SwDoc& m_rDoc;
88private:
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
105public:
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
152class CompareMainText : public CompareData
153{
154public:
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
166class CompareFrameFormatText : public CompareData
167{
168 const SwNodeIndex &m_rIndex;
169public:
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
182class 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
197public:
198 explicit Hash( sal_uLong nSize );
199
200 void CalcHashValue( CompareData& rData );
201
202 sal_uLong GetCount() const { return m_nCount; }
203};
204
205class Compare
206{
207public:
208 class MovedData
209 {
210 std::unique_ptr<sal_uLong[]> m_pIndex;
211 std::unique_ptr<sal_uLong[]> m_pLineNum;
212 sal_uLong m_nCount;
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
222private:
223 /// Look for the moved lines
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
245public:
246 Compare( sal_uLong nDiff, CompareData& rData1, CompareData& rData2 );
247};
248
249class ArrayComparator
250{
251public:
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
258/// Consider two lines equal if similar enough (e.g. look like different
259/// versions of the same paragraph)
260class LineArrayComparator : public ArrayComparator
261{
262private:
263 int m_nLen1, m_nLen2;
264 const CompareData &m_rData1, &m_rData2;
265 int m_nFirst1, m_nFirst2;
266
267public:
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
276class WordArrayComparator : public ArrayComparator
277{
278private:
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
285public:
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
295class CharArrayComparator : public ArrayComparator
296{
297private:
298 const SwTextNode *m_pTextNode1, *m_pTextNode2;
299
300public:
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
311/// Options set in Tools->Options->Writer->Comparison
312struct CmpOptionsContainer
313{
314 SwCompareMode eCmpMode;
315 int nIgnoreLen;
316 bool bUseRsid;
317};
318
319}
320
321static CmpOptionsContainer CmpOptions;
322
323namespace {
324
325class CommonSubseq
326{
327private:
328 std::unique_ptr<int[]> m_pData;
329
330protected:
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
342public:
343 static int IgnoreIsolatedPieces( int *pLcs1, int *pLcs2, int nLen1, int nLen2,
344 int nLcsLen, int nPieceLen );
345};
346
347/// Use Hirschberg's algorithm to find LCS in linear space
348class LgstCommonSubseq: public CommonSubseq
349{
350private:
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
360public:
361 explicit LgstCommonSubseq( ArrayComparator &rComparator );
362
363 int Find( int *pSubseq1, int *pSubseq2 );
364};
365
366/// Find a common subsequence in linear time
367class FastCommonSubseq: private CommonSubseq
368{
369private:
370 static const int CUTOFF = 2056;
371
372 int FindFastCS( int *pSeq1, int *pSeq2, int nStt1, int nEnd1,
373 int nStt2, int nEnd2 );
374
375public:
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
390CompareData::~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
406void 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
417void 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
428void 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
444sal_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
475bool 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
494Hash::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
544void Hash::CalcHashValue( CompareData& rData )
545{
546 if( !m_pHashArr )
547 return;
548
549 for( size_t n = 0; n < rData.GetLineCount(); ++n )
550 {
551 const SwCompareLine* pLine = rData.GetLine( n );
552 OSL_ENSURE( pLine, "where is the line?" )do { if (true && (!(pLine))) { sal_detail_logFormat((
SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"), ("/home/maarten/src/libreoffice/core/sw/source/core/doc/doccomp.cxx"
":" "552" ": "), "%s", "where is the line?"); } } while (false
)
;
553 sal_uLong nH = pLine->GetHashValue();
554
555 sal_uLong* pFound = &m_pHashArr[ nH % m_nPrime ];
556 size_t i;
557 for( i = *pFound; ; i = m_pDataArr[i].nNext )
558 if( !i )
559 {
560 i = m_nCount++;
561 m_pDataArr[i].nNext = *pFound;
562 m_pDataArr[i].nHash = nH;
563 m_pDataArr[i].pLine = pLine;
564 *pFound = i;
565 break;
566 }
567 else if( m_pDataArr[i].nHash == nH &&
568 m_pDataArr[i].pLine->Compare( *pLine ))
569 break;
570
571 rData.SetIndex( n, i );
572 }
573}
574
575Compare::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
611void 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
621void 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
645void 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;
654 sal_uLong length;
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
757Compare::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
783/// Find the differing lines
784Compare::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
797void 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
847sal_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_MAX2147483647;
904 else
905 ++bmin;
906 if (bmax < dmax)
907 m_pBDiag[++bmax + 1] = INT_MAX2147483647;
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
935namespace
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(9223372036854775807L *2UL+1UL);
943 sal_uLong other_preceding = ULONG_MAX(9223372036854775807L *2UL+1UL);
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
1005void Compare::ShiftBoundaries( CompareData& rData1, CompareData& rData2 )
1006{
1007 lcl_ShiftBoundariesOneway(&rData1, &rData2);
1008 lcl_ShiftBoundariesOneway(&rData2, &rData1);
1009}
1010
1011sal_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
1050const 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
1072bool SwCompareLine::Compare( const SwCompareLine& rLine ) const
1073{
1074 return CompareNode( m_rNode, rLine.m_rNode );
1075}
1076
1077namespace
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
1100bool 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
1151 case SectionType::ToxHeader:
1152 case SectionType::ToxContent:
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
1195OUString 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
1224 case SectionType::ToxHeader:
1225 case SectionType::ToxContent:
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
1253sal_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
1261bool 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
1274bool 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& rDstDoc = 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 = rDstDoc.GetIDocumentUndoRedo().DoesUndo();
1380 rDstDoc.GetIDocumentUndoRedo().DoUndo( false );
1381 SwPaM aCpyPam( rSrcNd, nSrcFrom );
1382 aCpyPam.SetMark();
1383 aCpyPam.GetPoint()->nContent = nSrcTo;
1384 aCpyPam.GetDoc().getIDocumentContentOperations().CopyRange( aCpyPam, *aPam.GetPoint(),
1385 SwCopyFlags::CheckPosInFly);
1386 rDstDoc.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
1411sal_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
1429sal_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
1447void 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
1500void CompareData::ShowInsert( sal_uLong nStt, sal_uLong nEnd )
1501{
1502 SwPaM* pTmp = new SwPaM( GetLine( nStt )->GetNode(), 0,
1
Memory is allocated
1503 GetLine( nEnd-1 )->GetEndNode(), 0,
1504 m_pInsertRing.get() );
1505 if( !m_pInsertRing )
2
Taking false branch
1506 m_pInsertRing.reset( pTmp );
1507
1508 // #i65201#: These SwPaMs are calculated smaller than needed, see comment below
1509}
3
Potential leak of memory pointed to by 'pTmp'
1510
1511void 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
1575void 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
1628void 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")do { if (true && (!(pDocShell))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"), ("/home/maarten/src/libreoffice/core/sw/source/core/doc/doccomp.cxx"
":" "1636" ": "), "%s", "no SwDocShell"); } } while (false)
;
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")do { if (true && (!(xDocProps.is()))) { sal_detail_logFormat
((SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"), ("/home/maarten/src/libreoffice/core/sw/source/core/doc/doccomp.cxx"
":" "1642" ": "), "%s", "Doc has no DocumentProperties"); } }
while (false)
;
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 {
1697 m_rDoc.GetIDocumentUndoRedo().AppendUndo(
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 return;
1708
1709 do {
1710 if( pTmp->GetPoint()->nContent == 0 )
1711 {
1712 ++pTmp->GetPoint()->nNode;
1713 pTmp->GetPoint()->nContent.Assign( pTmp->GetContentNode(), 0 );
1714 }
1715 // #i101009#
1716 // prevent redlines that end on structural end node
1717 if (& GetEndOfContent() ==
1718 & pTmp->GetPoint()->nNode.GetNode())
1719 {
1720 --pTmp->GetPoint()->nNode;
1721 SwContentNode *const pContentNode( pTmp->GetContentNode() );
1722 pTmp->GetPoint()->nContent.Assign( pContentNode,
1723 pContentNode ? pContentNode->Len() : 0 );
1724 // tdf#106218 try to avoid losing a paragraph break here:
1725 if (pTmp->GetMark()->nContent == 0)
1726 {
1727 SwNodeIndex const prev(pTmp->GetMark()->nNode, -1);
1728 if (prev.GetNode().IsTextNode())
1729 {
1730 *pTmp->GetMark() = SwPosition(
1731 *prev.GetNode().GetTextNode(),
1732 prev.GetNode().GetTextNode()->Len());
1733 }
1734 }
1735 }
1736 } while( m_pInsertRing.get() != ( pTmp = pTmp->GetNext()) );
1737 SwRedlineData aRedlnData( RedlineType::Insert, nAuthor, aTimeStamp,
1738 OUString(), nullptr );
1739
1740 // combine consecutive
1741 if( pTmp->GetNext() != m_pInsertRing.get() )
1742 {
1743 do {
1744 SwPosition& rSttEnd = *pTmp->End(),
1745 & rEndStt = *pTmp->GetNext()->Start();
1746 const SwContentNode* pCNd;
1747 if( rSttEnd == rEndStt ||
1748 (!rEndStt.nContent.GetIndex() &&
1749 rEndStt.nNode.GetIndex() - 1 == rSttEnd.nNode.GetIndex() &&
1750 nullptr != ( pCNd = rSttEnd.nNode.GetNode().GetContentNode() ) &&
1751 rSttEnd.nContent.GetIndex() == pCNd->Len()))
1752 {
1753 if( pTmp->GetNext() == m_pInsertRing.get() )
1754 {
1755 // are consecutive, so combine
1756 rEndStt = *pTmp->Start();
1757 delete pTmp;
1758 pTmp = m_pInsertRing.get();
1759 }
1760 else
1761 {
1762 // are consecutive, so combine
1763 rSttEnd = *pTmp->GetNext()->End();
1764 delete pTmp->GetNext();
1765 }
1766 }
1767 else
1768 pTmp = pTmp->GetNext();
1769 } while( m_pInsertRing.get() != pTmp );
1770 }
1771
1772 do {
1773 if (IDocumentRedlineAccess::AppendResult::APPENDED ==
1774 m_rDoc.getIDocumentRedlineAccess().AppendRedline(
1775 new SwRangeRedline(aRedlnData, *pTmp), true) &&
1776 m_rDoc.GetIDocumentUndoRedo().DoesUndo())
1777 {
1778 m_rDoc.GetIDocumentUndoRedo().AppendUndo(
1779 std::make_unique<SwUndoCompDoc>( *pTmp, true ));
1780 }
1781 } while( m_pInsertRing.get() != ( pTmp = pTmp->GetNext()) );
1782}
1783
1784typedef std::shared_ptr<CompareData> CompareDataPtr;
1785typedef std::pair<CompareDataPtr, CompareDataPtr> CompareDataPtrPair;
1786typedef std::vector<CompareDataPtrPair> Comparators;
1787
1788namespace
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
1832long 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()( static_cast<SwModule*>(SfxApplication::GetModule(SfxToolsModule
::Writer)))
->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()( static_cast<SwModule*>(SfxApplication::GetModule(SfxToolsModule
::Writer)))
->IsUseRsid();
1859 CmpOptions.nIgnoreLen = SW_MOD()( static_cast<SwModule*>(SfxApplication::GetModule(SfxToolsModule
::Writer)))
->IsIgnorePieces() ? SW_MOD()( static_cast<SwModule*>(SfxApplication::GetModule(SfxToolsModule
::Writer)))
->GetPieceLen() : 0;
1860 }
1861
1862 GetIDocumentUndoRedo().StartUndo(SwUndoId::EMPTY, nullptr);
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();
1868 rSrcDoc.getIDocumentRedlineAccess().SetRedlineFlags( RedlineFlags::ShowInsert );
1869 getIDocumentRedlineAccess().SetRedlineFlags(RedlineFlags::On | RedlineFlags::ShowInsert);
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 {
1883 getIDocumentRedlineAccess().SetRedlineFlags(RedlineFlags::On |
1884 RedlineFlags::ShowInsert | RedlineFlags::ShowDelete);
1885
1886 for (auto& a : aComparisons)
1887 {
1888 CompareData& rD1 = *a.second;
1889 rD1.SetRedlinesToDoc( !bDocWasModified );
1890 }
1891 getIDocumentState().SetModified();
1892 }
1893
1894 rSrcDoc.getIDocumentRedlineAccess().SetRedlineFlags( eSrcRedlMode );
1895 getIDocumentRedlineAccess().SetRedlineFlags(RedlineFlags::ShowInsert | RedlineFlags::ShowDelete);
1896
1897 if( !bSrcModified )
1898 rSrcDoc.getIDocumentState().ResetModified();
1899
1900 GetIDocumentUndoRedo().EndUndo(SwUndoId::EMPTY, nullptr);
1901
1902 return nRet;
1903}
1904
1905namespace
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
1916SaveMergeRedline::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 return;
1929
1930 // mark the area as deleted
1931 const SwPosition* pEnd = pStt == rSrcRedl.GetPoint()
1932 ? rSrcRedl.GetMark()
1933 : rSrcRedl.GetPoint();
1934
1935 pDestRedl->SetMark();
1936 pDestRedl->GetPoint()->nNode += pEnd->nNode.GetIndex() -
1937 pStt->nNode.GetIndex();
1938 pDestRedl->GetPoint()->nContent.Assign( pDestRedl->GetContentNode(),
1939 pEnd->nContent.GetIndex() );
1940}
1941
1942sal_uInt16 SaveMergeRedline::InsertRedline(SwPaM* pLastDestRedline)
1943{
1944 sal_uInt16 nIns = 0;
1945 SwDoc& rDoc = 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(rDoc.GetIDocumentUndoRedo());
1951
1952 SwNodeIndex aSaveNd( pDestRedl->GetPoint()->nNode, -1 );
1953 const sal_Int32 nSaveCnt = pDestRedl->GetPoint()->nContent.GetIndex();
1954
1955 RedlineFlags eOld = rDoc.getIDocumentRedlineAccess().GetRedlineFlags();
1956 rDoc.getIDocumentRedlineAccess().SetRedlineFlags_intern(eOld | RedlineFlags::Ignore);
1957
1958 pSrcRedl->GetDoc().getIDocumentContentOperations().CopyRange(
1959 *const_cast<SwPaM*>(static_cast<const SwPaM*>(pSrcRedl)),
1960 *pDestRedl->GetPoint(), SwCopyFlags::CheckPosInFly);
1961
1962 rDoc.getIDocumentRedlineAccess().SetRedlineFlags_intern( eOld );
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();
1979 SwRedlineTable::size_type n = 0;
1980
1981 // find the first redline for StartPos
1982 if( !rDoc.getIDocumentRedlineAccess().GetRedline( *pDStt, &n ) && n )
1983 --n;
1984
1985 const SwRedlineTable& rRedlineTable = rDoc.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 {
1998 case SwComparePosition::CollideStart:
1999 case SwComparePosition::Behind:
2000 break;
2001
2002 case SwComparePosition::Inside:
2003 case SwComparePosition::Equal:
2004 delete pDestRedl;
2005 pDestRedl = nullptr;
2006 [[fallthrough]];
2007
2008 case SwComparePosition::CollideEnd:
2009 case SwComparePosition::Before:
2010 n = rRedlineTable.size();
2011 break;
2012
2013 case SwComparePosition::Outside:
2014 assert(pDestRedl && "is this actually impossible")(static_cast <bool> (pDestRedl && "is this actually impossible"
) ? void (0) : __assert_fail ("pDestRedl && \"is this actually impossible\""
, "/home/maarten/src/libreoffice/core/sw/source/core/doc/doccomp.cxx"
, 2014, __extension__ __PRETTY_FUNCTION__))
;
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 (rDoc.GetIDocumentUndoRedo().DoesUndo())
2024 pUndo.reset(new SwUndoCompDoc( *pCpyRedl ));
2025
2026 // now modify doc: append redline, undo (and count)
2027 rDoc.getIDocumentRedlineAccess().AppendRedline( pCpyRedl, true );
2028 if( pUndo )
2029 {
2030 rDoc.GetIDocumentUndoRedo().AppendUndo(std::move(pUndo));
2031 }
2032 ++nIns;
2033
2034 *pDStt = *pREnd;
2035
2036 // we should start over now
2037 n = SwRedlineTable::npos;
2038 }
2039 break;
2040
2041 case SwComparePosition::OverlapBefore:
2042 *pDEnd = *pRStt;
2043 break;
2044
2045 case SwComparePosition::OverlapBehind:
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 (rDoc.GetIDocumentUndoRedo().DoesUndo())
2060 pUndo.reset(new SwUndoCompDoc( *pDestRedl ));
2061
2062 // now modify doc: append redline, undo (and count)
2063 IDocumentRedlineAccess::AppendResult const result(
2064 rDoc.getIDocumentRedlineAccess().AppendRedline(pDestRedl, true));
2065 if( pUndo )
2066 {
2067 rDoc.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
2073 if (IDocumentRedlineAccess::AppendResult::APPENDED != result)
2074 pDestRedl = nullptr;
2075 }
2076 return nIns;
2077}
2078
2079/// Merge two documents
2080long SwDoc::MergeDoc( const SwDoc& rDoc )
2081{
2082 if( &rDoc == this )
2083 return 0;
2084
2085 long nRet = 0;
2086
2087 GetIDocumentUndoRedo().StartUndo(SwUndoId::EMPTY, nullptr);
2088
2089 SwDoc& rSrcDoc = const_cast<SwDoc&>(rDoc);
2090 bool bSrcModified = rSrcDoc.getIDocumentState().IsModified();
2091
2092 RedlineFlags eSrcRedlMode = rSrcDoc.getIDocumentRedlineAccess().GetRedlineFlags();
2093 rSrcDoc.getIDocumentRedlineAccess().SetRedlineFlags( RedlineFlags::ShowDelete );
2094 getIDocumentRedlineAccess().SetRedlineFlags( RedlineFlags::ShowDelete );
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
2127 rSrcDoc.getIDocumentRedlineAccess().SetRedlineFlags(RedlineFlags::ShowInsert | RedlineFlags::ShowDelete);
2128
2129 getIDocumentRedlineAccess().SetRedlineFlags(
2130 RedlineFlags::On |
2131 RedlineFlags::ShowInsert |
2132 RedlineFlags::ShowDelete);
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
2147 getIDocumentRedlineAccess().SetRedlineFlags(RedlineFlags::ShowInsert | RedlineFlags::ShowDelete);
2148
2149 GetIDocumentUndoRedo().EndUndo(SwUndoId::EMPTY, nullptr);
2150
2151 return nRet;
2152}
2153
2154LineArrayComparator::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
2163bool 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!" )do { if (true && (!(false))) { sal_detail_logFormat((
SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"), ("/home/maarten/src/libreoffice/core/sw/source/core/doc/doccomp.cxx"
":" "2167" ": "), "%s", "Index out of range!"); } } while (false
)
;
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
2241bool 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!" )do { if (true && (!(false))) { sal_detail_logFormat((
SAL_DETAIL_LOG_LEVEL_WARN), ("legacy.osl"), ("/home/maarten/src/libreoffice/core/sw/source/core/doc/doccomp.cxx"
":" "2245" ": "), "%s", "Index out of range!"); } } while (false
)
;
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
2254WordArrayComparator::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
2265bool 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
2285int 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
2315void 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
2331int 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 )(static_cast <bool> (nLen1 >= 0) ? void (0) : __assert_fail
("nLen1 >= 0", "/home/maarten/src/libreoffice/core/sw/source/core/doc/doccomp.cxx"
, 2337, __extension__ __PRETTY_FUNCTION__))
;
2338 assert( nLen2 >= 0 )(static_cast <bool> (nLen2 >= 0) ? void (0) : __assert_fail
("nLen2 >= 0", "/home/maarten/src/libreoffice/core/sw/source/core/doc/doccomp.cxx"
, 2338, __extension__ __PRETTY_FUNCTION__))
;
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
2393int 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
2444LgstCommonSubseq::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
2454void 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 )(static_cast <bool> (false) ? void (0) : __assert_fail (
"false", "/home/maarten/src/libreoffice/core/sw/source/core/doc/doccomp.cxx"
, 2466, __extension__ __PRETTY_FUNCTION__))
;
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
2490int 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
2534int 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
2572int 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: */