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