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