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