src/Compare.cpp

   1 /**
   2  * \file Compare.cpp
   3  * This file is part of LyX, the document processor.
   4  * Licence details can be found in the file COPYING.
   5  *
   6  * \author Vincent van Ravesteijn
   7  *
   8  * Full author contact details are available in file CREDITS.
   9  */
  10
  11 #include <config.h>
  12
  13 #include "Compare.h"
  14
  15 #include "Author.h"
  16 #include "BufferParams.h"
  17 #include "Changes.h"
  18 #include "Font.h"
  19
  20 #include "insets/InsetText.h"
  21
  22 #include "support/lassert.h"
  23 #include "support/qstring_helpers.h"
  24
  25 #include <boost/next_prior.hpp>
  26
  27 using namespace std;
  28 using namespace lyx::support;
  29
  30
  31 namespace lyx {
  32
  33
  34 enum Direction {
  35         Forward = 0,
  36         Backward
  37 };
  38
  39
  40 static void step(DocIterator & dit, Direction direction)
  41 {
  42         if (direction == Forward)
  43                 dit.top().forwardPos();
  44         else
  45                 dit.top().backwardPos();
  46 }
  47
  48
  49 static void step(DocIterator & dit, DocIterator const & end, Direction direction)
  50 {
  51         if (dit != end)
  52                 step(dit, direction);
  53 }
  54
  55
  56 /**
  57  * A pair of two DocIterators that form a range.
  58  */
  59 class DocRange {
  60 public:
  61         DocRange(DocIterator const & from_, DocIterator const & to_)
  62                 : from(from_), to(to_)
  63         {}
  64
  65         DocRange(Buffer const * buf)
  66         {
  67                 from = doc_iterator_begin(buf);
  68                 to = doc_iterator_end(buf);
  69                 to.backwardPos();
  70         }
  71
  72         ///
  73         Text * text() const { return from.text(); }
  74         ///
  75         bool empty() const { return to <= from; }
  76         ///
  77         size_t length() const;
  78
  79         /// The begin of the range
  80         DocIterator from;
  81         /// The end of the range
  82         DocIterator to;
  83 };
  84
  85
  86 size_t DocRange::length() const
  87 {
  88         ParagraphList const & ps = from.text()->paragraphs();
  89         size_t length = 0;
  90         pit_type pit = from.pit();
  91         pit_type const endpit = to.pit();
  92         for (; pit < endpit; ++pit)
  93                 length += ps[pit].size() + 1;
  94         length += to.pos() - from.pos();
  95         return length;
  96 }
  97
  98
  99 class DocPair {
 100 public:
 101         DocPair()
 102         {}
 103
 104         DocPair(DocIterator o_, DocIterator n_)
 105                 : o(o_), n(n_)
 106         {}
 107
 108         bool operator!=(DocPair const & rhs)
 109         {
 110                 // this might not be intuitive but correct for our purpose
 111                 return o != rhs.o && n != rhs.n;
 112         }
 113
 114
 115         DocPair & operator++()
 116         {
 117                 step(o, Forward);
 118                 step(n, Forward);
 119                 return *this;
 120         }
 121
 122         DocPair & operator--()
 123         {
 124                 step(o, Backward);
 125                 step(n, Backward);
 126                 return *this;
 127         }
 128         ///
 129         DocIterator o;
 130         ///
 131         DocIterator n;
 132 };
 133
 134 /**
 135  * A pair of two DocRanges.
 136  */
 137 class DocRangePair {
 138 public:
 139         DocRangePair(DocRange const & o_, DocRange const & n_)
 140                 : o(o_), n(n_)
 141         {}
 142
 143         DocRangePair(DocPair const & from, DocPair const & to)
 144                 : o(from.o, to.o), n(from.n, to.n)
 145         {}
 146
 147         DocRangePair(Buffer const * o_buf, Buffer const * n_buf)
 148                 : o(o_buf), n(n_buf)
 149         {}
 150
 151         /// Returns the from pair
 152         DocPair from() const
 153         {
 154                 return DocPair(o.from, n.from);
 155         }
 156
 157         /// Returns the to pair
 158         DocPair to() const
 159         {
 160                 return DocPair(o.to, n.to);
 161         }
 162
 163         DocRange o;
 164         DocRange n;
 165 };
 166
 167
 168 static DocRangePair stepIntoInset(DocPair const & inset_location)
 169 {
 170         DocRangePair rp(inset_location, inset_location);
 171         rp.o.from.forwardPos();
 172         rp.n.from.forwardPos();
 173         step(rp.o.to, Forward);
 174         step(rp.n.to, Forward);
 175         rp.o.to.backwardPos();
 176         rp.n.to.backwardPos();
 177         return rp;
 178 }
 179
 180
 181 /**
 182  *  This class is designed to hold a vector that has both positive as
 183  *  negative indices. It is internally represented as two vectors, one
 184  *  for non-zero indices and one for negative indices. In this way, the
 185  *  vector can grow in both directions.
 186  *    If an index is not available in the vector, the default value is
 187  *  returned. If an object is put in the vector beyond its size, the
 188  *  empty spots in between are also filled with the default value.
 189  */
 190 template<class T>
 191 class compl_vector {
 192 public:
 193         compl_vector()
 194         {}
 195
 196         void reset(T const & def)
 197         {
 198                 default_ = def;
 199                 Vp_.clear();
 200                 Vn_.clear();
 201         }
 202
 203         /// Gets the value at index. If it is not in the vector
 204         /// the default value is inserted and returned.
 205         T & operator[](int index) {
 206                 vector<T> & V = index >= 0 ? Vp_ : Vn_;
 207                 unsigned int const ii = index >= 0 ? index : -index - 1;
 208                 while (ii >= V.size())
 209                         V.push_back(default_);
 210                 return V[ii];
 211         }
 212
 213 private:
 214         /// The vector for positive indices
 215         vector<T> Vp_;
 216         /// The vector for negative indices
 217         vector<T> Vn_;
 218         /// The default value that is inserted in the vector
 219         /// if more space is needed
 220         T default_;
 221 };
 222
 223
 224 /**
 225  * The implementation of the algorithm that does the comparison
 226  * between two documents.
 227  */
 228 class Compare::Impl {
 229 public:
 230         ///
 231         Impl(Compare const & compare)
 232                 : abort_(false), N_(0), M_(0), offset_reverse_diagonal_(0),
 233                   odd_offset_(0), compare_(compare),
 234                   old_buf_(0), new_buf_(0), dest_buf_(0), dest_pars_(0),
 235                   recursion_level_(0), nested_inset_level_(0), D_(0)
 236         {}
 237
 238         ///
 239         ~Impl()
 240         {}
 241
 242         // Algorithm to find the shortest edit string. This algorithm
 243         // only needs a linear amount of memory (linear with the sum
 244         // of the number of characters in the two paragraph-lists).
 245         bool diff(Buffer const * new_buf, Buffer const * old_buf,
 246                 Buffer const * dest_buf);
 247
 248         /// Set to true to cancel the algorithm
 249         bool abort_;
 250
 251         ///
 252         QString status()
 253         {
 254                 QString status;
 255                 status += toqstr("recursion level:") + " " + QString::number(recursion_level_)
 256                         + " " + toqstr("differences:") + " " + QString::number(D_);
 257                 return status;
 258         }
 259
 260 private:
 261         /// Finds the middle snake and returns the length of the
 262         /// shortest edit script.
 263         int findMiddleSnake(DocRangePair const & rp, DocPair & middle_snake);
 264
 265         enum SnakeResult {
 266                 NoSnake,
 267                 SingleSnake,
 268                 NormalSnake
 269         };
 270
 271         /// Retrieve the middle snake when there is overlap between
 272         /// the forward and backward path.
 273         SnakeResult retrieveMiddleSnake(int k, int D, Direction direction,
 274                 DocPair & middle_snake);
 275
 276         /// Find the furthest reaching D-path (number of horizontal
 277         /// and vertical steps; differences between the old and new
 278         /// document) in the k-diagonal (vertical minus horizontal steps).
 279         void furthestDpathKdiagonal(int D, int k,
 280                 DocRangePair const & rp, Direction direction);
 281
 282         /// Is there overlap between the forward and backward path
 283         bool overlap(int k, int D);
 284
 285         /// This function is called recursively by a divide and conquer
 286         /// algorithm. Each time, the string is divided into two split
 287         /// around the middle snake.
 288         void diff_i(DocRangePair const & rp);
 289
 290         /// Processes the split chunks. It either adds them as deleted,
 291         /// as added, or call diff_i for further processing.
 292         void diffPart(DocRangePair const & rp);
 293
 294         /// Runs the algorithm for the inset located at /c it and /c it_n
 295         /// and adds the result to /c pars.
 296         void diffInset(Inset * inset, DocPair const & p);
 297
 298         /// Adds the snake to the destination buffer. The algorithm will
 299         /// recursively be applied to any InsetTexts that are within the snake.
 300         void processSnake(DocRangePair const & rp);
 301
 302         /// Writes the range to the destination buffer
 303         void writeToDestBuffer(DocRange const & range,
 304                 Change::Type type = Change::UNCHANGED);
 305
 306         /// Writes the paragraph list to the destination buffer
 307         void writeToDestBuffer(ParagraphList const & copy_pars) const;
 308
 309         /// The length of the old chunk currently processed
 310         int N_;
 311         /// The length of the new chunk currently processed
 312         int M_;
 313         /// The offset diagonal of the reverse path of the
 314         /// currently processed chunk
 315         int offset_reverse_diagonal_;
 316         /// Is the offset odd or even ?
 317         bool odd_offset_;
 318
 319         /// The thread object, used to emit signals to the GUI
 320         Compare const & compare_;
 321
 322         /// The buffer containing text that will be marked as old
 323         Buffer const * old_buf_;
 324         /// The buffer containing text that will be marked as new
 325         Buffer const * new_buf_;
 326         /// The buffer containing text that will be marked as new
 327         Buffer const * dest_buf_;
 328
 329         /// The paragraph list of the destination buffer
 330         ParagraphList * dest_pars_;
 331
 332         /// The level of recursion
 333         int recursion_level_;
 334
 335         /// The number of nested insets at this level
 336         int nested_inset_level_;
 337
 338         /// The position/snake in the old/new document
 339         /// of the forward/reverse search
 340         compl_vector<DocIterator> ofp;
 341         compl_vector<DocIterator> nfp;
 342         compl_vector<DocIterator> ofs;
 343         compl_vector<DocIterator> nfs;
 344         compl_vector<DocIterator> orp;
 345         compl_vector<DocIterator> nrp;
 346         compl_vector<DocIterator> ors;
 347         compl_vector<DocIterator> nrs;
 348
 349         /// The number of differences in the path the algorithm
 350         /// is currently processing.
 351         int D_;
 352 };
 353
 354 /////////////////////////////////////////////////////////////////////
 355 //
 356 // Compare
 357 //
 358 /////////////////////////////////////////////////////////////////////
 359
 360 Compare::Compare(Buffer const * new_buf, Buffer const * old_buf,
 361         Buffer * const dest_buf, CompareOptions const & options)
 362         : new_buffer(new_buf), old_buffer(old_buf), dest_buffer(dest_buf),
 363           options_(options), pimpl_(new Impl(*this))
 364 {
 365         connect(&status_timer_, SIGNAL(timeout()),
 366                 this, SLOT(doStatusMessage()));
 367         status_timer_.start(1000);
 368 }
 369
 370
 371 void Compare::doStatusMessage()
 372 {
 373         statusMessage(pimpl_->status());
 374 }
 375
 376
 377 void Compare::run()
 378 {
 379         if (!dest_buffer || !new_buffer || !old_buffer)
 380                 return;
 381
 382         // Copy the buffer params to the destination buffer
 383         dest_buffer->params() = options_.settings_from_new
 384                 ? new_buffer->params() : old_buffer->params();
 385
 386         // Copy extra authors to the destination buffer
 387         AuthorList const & extra_authors = options_.settings_from_new ?
 388                 old_buffer->params().authors() : new_buffer->params().authors();
 389         AuthorList::Authors::const_iterator it = extra_authors.begin();
 390         for (; it != extra_authors.end(); ++it)
 391                 dest_buffer->params().authors().record(*it);
 392
 393         doStatusMessage();
 394
 395         // do the real work
 396         if (!doCompare())
 397                 return;
 398
 399         finished(pimpl_->abort_);
 400         return;
 401 }
 402
 403
 404 int Compare::doCompare()
 405 {
 406         return pimpl_->diff(new_buffer, old_buffer, dest_buffer);
 407 }
 408
 409
 410 void Compare::abort()
 411 {
 412         pimpl_->abort_ = true;
 413         condition_.wakeOne();
 414         wait();
 415         pimpl_->abort_ = false;
 416 }
 417
 418
 419 static void getParagraphList(DocRange const & range,
 420         ParagraphList & pars)
 421 {
 422         // Clone the paragraphs within the selection.
 423         pit_type startpit = range.from.pit();
 424         pit_type endpit = range.to.pit();
 425         ParagraphList const & ps_ = range.text()->paragraphs();
 426         ParagraphList tmp_pars(boost::next(ps_.begin(), startpit),
 427                 boost::next(ps_.begin(), endpit + 1));
 428
 429         // Remove the end of the last paragraph; afterwards, remove the
 430         // beginning of the first paragraph. Keep this order - there may only
 431         // be one paragraph!
 432         Paragraph & back = tmp_pars.back();
 433         back.eraseChars(range.to.pos(), back.size(), false);
 434         Paragraph & front = tmp_pars.front();
 435         front.eraseChars(0, range.from.pos(), false);
 436
 437         pars.insert(pars.begin(), tmp_pars.begin(), tmp_pars.end());
 438 }
 439
 440
 441 static bool equal(Inset const * i_o, Inset const * i_n)
 442 {
 443         if (!i_o || !i_n)
 444                 return false;
 445
 446         // Different types of insets
 447         if (i_o->lyxCode() != i_n->lyxCode())
 448                 return false;
 449
 450         // Editable insets are assumed to be the same as they are of the
 451         // same type. If we later on decide that we insert them in the
 452         // document as being unchanged, we will run the algorithm on the
 453         // contents of the two insets.
 454         // FIXME: This fails if the parameters of the insets differ.
 455         // FIXME: We do not recurse into InsetTabulars.
 456         // FIXME: We need methods inset->equivalent(inset).
 457         if (i_o->editable() && !i_o->asInsetMath()
 458                   && i_o->asInsetText())
 459                 return true;
 460
 461         ostringstream o_os;
 462         ostringstream n_os;
 463         i_o->write(o_os);
 464         i_n->write(n_os);
 465         return o_os.str() == n_os.str();
 466 }
 467
 468
 469 static bool equal(DocIterator & o, DocIterator & n)
 470 {
 471         // Explicitly check for this, so we won't call
 472         // Paragraph::getChar for the last pos.
 473         bool const o_lastpos = o.pos() == o.lastpos();
 474         bool const n_lastpos = n.pos() == n.lastpos();
 475         if (o_lastpos || n_lastpos)
 476                 return o_lastpos && n_lastpos;
 477
 478         Paragraph const & old_par = o.text()->getPar(o.pit());
 479         Paragraph const & new_par = n.text()->getPar(n.pit());
 480
 481         char_type const c_o = old_par.getChar(o.pos());
 482         char_type const c_n = new_par.getChar(n.pos());
 483         if (c_o != c_n)
 484                 return false;
 485
 486         if (old_par.isInset(o.pos())) {
 487                 Inset const * i_o = old_par.getInset(o.pos());
 488                 Inset const * i_n = new_par.getInset(n.pos());
 489
 490                 if (i_o && i_n)
 491                         return equal(i_o, i_n);
 492         }
 493
 494         Font fo = old_par.getFontSettings(o.buffer()->params(), o.pos());
 495         Font fn = new_par.getFontSettings(n.buffer()->params(), n.pos());
 496         return fo == fn;
 497 }
 498
 499
 500 /// Traverses a snake in a certain direction. p points to a
 501 /// position in the old and new file and they are synchronously
 502 /// moved along the snake. The function returns true if a snake
 503 /// was found.
 504 static bool traverseSnake(DocPair & p, DocRangePair const & range,
 505         Direction direction)
 506 {
 507         bool ret = false;
 508         DocPair const & p_end =
 509                 direction == Forward ? range.to() : range.from();
 510
 511         while (p != p_end) {
 512                 if (direction == Backward)
 513                         --p;
 514                 if (!equal(p.o, p.n)) {
 515                         if (direction == Backward)
 516                                 ++p;
 517                         return ret;
 518                 }
 519                 if (direction == Forward)
 520                         ++p;
 521                 ret = true;
 522         }
 523         return ret;
 524 }
 525
 526
 527 /////////////////////////////////////////////////////////////////////
 528 //
 529 // Compare::Impl
 530 //
 531 /////////////////////////////////////////////////////////////////////
 532
 533
 534 void Compare::Impl::furthestDpathKdiagonal(int D, int k,
 535          DocRangePair const & rp, Direction direction)
 536 {
 537         compl_vector<DocIterator> & op = direction == Forward ? ofp : orp;
 538         compl_vector<DocIterator> & np = direction == Forward ? nfp : nrp;
 539         compl_vector<DocIterator> & os = direction == Forward ? ofs : ors;
 540         compl_vector<DocIterator> & ns = direction == Forward ? nfs : nrs;
 541
 542         // A vertical step means stepping one character in the new document.
 543         bool vertical_step = k == -D;
 544         if (!vertical_step && k != D) {
 545                 vertical_step = direction == Forward
 546                         ? op[k - 1] < op[k + 1] : op[k - 1] > op[k + 1];
 547         }
 548
 549         // Where do we take the step from ?
 550         int const kk = vertical_step ? k + 1 : k - 1;
 551         DocPair p(op[kk], np[kk]);
 552         DocPair const s(os[kk], ns[kk]);
 553
 554         // If D==0 we simulate a vertical step from (0,-1) by doing nothing.
 555         if (D != 0) {
 556                 // Take a step
 557                 if (vertical_step && direction == Forward)
 558                         step(p.n, rp.n.to, direction);
 559                 else if (vertical_step && direction == Backward)
 560                         step(p.n, rp.n.from, direction);
 561                 else if (!vertical_step && direction == Forward)
 562                         step(p.o, rp.o.to, direction);
 563                 else if (!vertical_step && direction == Backward)
 564                         step(p.o, rp.o.from, direction);
 565         }
 566
 567         // Traverse snake
 568         if (traverseSnake(p, rp, direction)) {
 569                 // Record last snake
 570                 os[k] = p.o;
 571                 ns[k] = p.n;
 572         } else {
 573                 // Copy last snake from the previous step
 574                 os[k] = s.o;
 575                 ns[k] = s.n;
 576         }
 577
 578         //Record new position
 579         op[k] = p.o;
 580         np[k] = p.n;
 581 }
 582
 583
 584 bool Compare::Impl::overlap(int k, int D)
 585 {
 586         // To generalize for the forward and reverse checks
 587         int kk = offset_reverse_diagonal_ - k;
 588
 589         // Can we have overlap ?
 590         if (kk <= D && kk >= -D) {
 591                 // Do we have overlap ?
 592                 if (odd_offset_)
 593                         return ofp[k] >= orp[kk] && nfp[k] >= nrp[kk];
 594                 else
 595                         return ofp[kk] >= orp[k] && nfp[kk] >= nrp[k];
 596         }
 597         return false;
 598 }
 599
 600
 601 Compare::Impl::SnakeResult Compare::Impl::retrieveMiddleSnake(
 602         int k, int D, Direction direction, DocPair & middle_snake)
 603 {
 604         compl_vector<DocIterator> & os = direction == Forward ? ofs : ors;
 605         compl_vector<DocIterator> & ns = direction == Forward ? nfs : nrs;
 606         compl_vector<DocIterator> & os_r = direction == Forward ? ors : ofs;
 607         compl_vector<DocIterator> & ns_r = direction == Forward ? nrs : nfs;
 608
 609         // The diagonal while doing the backward search
 610         int kk = -k + offset_reverse_diagonal_;
 611
 612         // Did we find a snake ?
 613         if (os[k].empty() && os_r[kk].empty()) {
 614                 // No, there is no snake at all, in which case
 615                 // the length of the shortest edit script is M+N.
 616                 LATTEST(2 * D - odd_offset_ == M_ + N_);
 617                 return NoSnake;
 618         }
 619
 620         if (os[k].empty()) {
 621                 // Yes, but there is only 1 snake and we found it in the
 622                 // reverse path.
 623                 middle_snake.o = os_r[kk];
 624                 middle_snake.n = ns_r[kk];
 625                 return SingleSnake;
 626         }
 627
 628         middle_snake.o = os[k];
 629         middle_snake.n = ns[k];
 630         return NormalSnake;
 631 }
 632
 633
 634 int Compare::Impl::findMiddleSnake(DocRangePair const & rp,
 635         DocPair & middle_snake)
 636 {
 637         // The lengths of the old and new chunks.
 638         N_ = rp.o.length();
 639         M_ = rp.n.length();
 640
 641         // Forward paths are centered around the 0-diagonal; reverse paths
 642         // are centered around the diagonal N - M. (Delta in the article)
 643         offset_reverse_diagonal_ = N_ - M_;
 644
 645         // If the offset is odd, only check for overlap while extending forward
 646     // paths, otherwise only check while extending reverse paths.
 647         odd_offset_ = (offset_reverse_diagonal_ % 2 != 0);
 648
 649         ofp.reset(rp.o.from);
 650         nfp.reset(rp.n.from);
 651         ofs.reset(DocIterator());
 652         nfs.reset(DocIterator());
 653         orp.reset(rp.o.to);
 654         nrp.reset(rp.n.to);
 655         ors.reset(DocIterator());
 656         nrs.reset(DocIterator());
 657
 658         // In the formula below, the "+ 1" ensures we round like ceil()
 659         int const D_max = (M_ + N_ + 1)/2;
 660         // D is the number of horizontal and vertical steps, i.e.
 661         // different characters in the old and new chunk.
 662         for (int D = 0; D <= D_max; ++D) {
 663                 // to be used in the status messages
 664                 D_ = D;
 665
 666                 // Forward and reverse paths
 667                 for (int f = 0; f < 2; ++f) {
 668                         Direction direction = f == 0 ? Forward : Backward;
 669
 670                         // Diagonals between -D and D can be reached by a D-path
 671                         for (int k = -D; k <= D; k += 2) {
 672                                 // Find the furthest reaching D-path on this diagonal
 673                                 furthestDpathKdiagonal(D, k, rp, direction);
 674
 675                                 // Only check for overlap for forward paths if the offset is odd
 676                                 // and only for reverse paths if the offset is even.
 677                                 if (odd_offset_ == (direction == Forward)) {
 678
 679                                         // Do the forward and backward paths overlap ?
 680                                         if (overlap(k, D - odd_offset_)) {
 681                                                 retrieveMiddleSnake(k, D, direction, middle_snake);
 682                                                 return 2 * D - odd_offset_;
 683                                         }
 684                                 }
 685                                 if (abort_)
 686                                         return 0;
 687                         }
 688                 }
 689         }
 690         // This should never be reached
 691         return -2;
 692 }
 693
 694
 695 bool Compare::Impl::diff(Buffer const * new_buf, Buffer const * old_buf,
 696         Buffer const * dest_buf)
 697 {
 698         if (!new_buf || !old_buf || !dest_buf)
 699                 return false;
 700
 701         old_buf_ = old_buf;
 702         new_buf_ = new_buf;
 703         dest_buf_ = dest_buf;
 704         dest_pars_ = &dest_buf->inset().asInsetText()->paragraphs();
 705         dest_pars_->clear();
 706
 707         recursion_level_ = 0;
 708         nested_inset_level_ = 0;
 709
 710         DocRangePair rp(old_buf_, new_buf_);
 711
 712         DocPair from = rp.from();
 713         traverseSnake(from, rp, Forward);
 714         DocRangePair const snake(rp.from(), from);
 715         processSnake(snake);
 716
 717         // Start the recursive algorithm
 718         DocRangePair rp_new(from, rp.to());
 719         if (!rp_new.o.empty() || !rp_new.n.empty())
 720                 diff_i(rp_new);
 721
 722         for (pit_type p = 0; p < (pit_type)dest_pars_->size(); ++p) {
 723                 (*dest_pars_)[p].setBuffer(const_cast<Buffer &>(*dest_buf));
 724                 (*dest_pars_)[p].setInsetOwner(&dest_buf_->inset());
 725         }
 726
 727         return true;
 728 }
 729
 730
 731 void Compare::Impl::diff_i(DocRangePair const & rp)
 732 {
 733         if (abort_)
 734                 return;
 735
 736         // The middle snake
 737         DocPair middle_snake;
 738
 739         // Divides the problem into two smaller problems, split around
 740         // the snake in the middle.
 741         int const L_ses = findMiddleSnake(rp, middle_snake);
 742
 743         // Set maximum of progress bar
 744         if (++recursion_level_ == 1)
 745                 compare_.progressMax(L_ses);
 746
 747         // There are now three possibilities: the strings were the same,
 748         // the strings were completely different, or we found a middle
 749         // snake and we can split the string into two parts to process.
 750         if (L_ses == 0)
 751                 // Two the same strings (this must be a very rare case, because
 752                 // usually this will be part of a snake adjacent to these strings).
 753                 writeToDestBuffer(rp.o);
 754
 755         else if (middle_snake.o.empty()) {
 756                 // Two totally different strings
 757                 writeToDestBuffer(rp.o, Change::DELETED);
 758                 writeToDestBuffer(rp.n, Change::INSERTED);
 759
 760         } else {
 761                 // Retrieve the complete snake
 762                 DocPair first_part_end = middle_snake;
 763                 traverseSnake(first_part_end, rp, Backward);
 764                 DocRangePair first_part(rp.from(), first_part_end);
 765
 766                 DocPair second_part_begin = middle_snake;
 767                 traverseSnake(second_part_begin, rp, Forward);
 768                 DocRangePair second_part(second_part_begin, rp.to());
 769
 770                 // Split the string in three parts:
 771                 // 1. in front of the snake
 772                 diffPart(first_part);
 773
 774                 // 2. the snake itself, and
 775                 DocRangePair const snake(first_part.to(), second_part.from());
 776                 processSnake(snake);
 777
 778                 // 3. behind the snake.
 779                 diffPart(second_part);
 780         }
 781         --recursion_level_;
 782 }
 783
 784
 785 void Compare::Impl::diffPart(DocRangePair const & rp)
 786 {
 787         // Is there a finite length string in both buffers, if not there
 788         // is an empty string and we write the other one to the buffer.
 789         if (!rp.o.empty() && !rp.n.empty())
 790                 diff_i(rp);
 791
 792         else if (!rp.o.empty())
 793                 writeToDestBuffer(rp.o, Change::DELETED);
 794
 795         else if (!rp.n.empty())
 796                 writeToDestBuffer(rp.n, Change::INSERTED);
 797 }
 798
 799
 800 void Compare::Impl::diffInset(Inset * inset, DocPair const & p)
 801 {
 802         // Find the dociterators for the beginning and the
 803         // end of the inset, for the old and new document.
 804         DocRangePair const rp = stepIntoInset(p);
 805
 806         // Recurse into the inset. Temporarily replace the dest_pars
 807         // paragraph list by the paragraph list of the nested inset.
 808         ParagraphList * backup_dest_pars = dest_pars_;
 809         dest_pars_ = &inset->asInsetText()->text().paragraphs();
 810         dest_pars_->clear();
 811
 812         ++nested_inset_level_;
 813         diff_i(rp);
 814         --nested_inset_level_;
 815
 816         dest_pars_ = backup_dest_pars;
 817 }
 818
 819
 820 void Compare::Impl::processSnake(DocRangePair const & rp)
 821 {
 822         ParagraphList pars;
 823         getParagraphList(rp.o, pars);
 824
 825         // Find insets in this paragaph list
 826         DocPair it = rp.from();
 827         for (; it.o < rp.o.to; ++it) {
 828                 Inset * inset = it.o.text()->getPar(it.o.pit()).getInset(it.o.pos());
 829                 if (inset && inset->editable() && inset->asInsetText()) {
 830                         // Find the inset in the paragraph list that will be pasted into
 831                         // the final document. The contents of the inset will be replaced
 832                         // by the output of the algorithm below.
 833                         pit_type const pit = it.o.pit() - rp.o.from.pit();
 834                         pos_type const pos = pit ? it.o.pos() : it.o.pos() - rp.o.from.pos();
 835                         inset = pars[pit].getInset(pos);
 836                         LASSERT(inset, continue);
 837                         diffInset(inset, it);
 838                 }
 839         }
 840         writeToDestBuffer(pars);
 841 }
 842
 843
 844 void Compare::Impl::writeToDestBuffer(DocRange const & range,
 845         Change::Type type)
 846 {
 847         ParagraphList pars;
 848         getParagraphList(range, pars);
 849
 850         pos_type size = 0;
 851
 852         // Set the change
 853         ParagraphList::iterator it = pars.begin();
 854         for (; it != pars.end(); ++it) {
 855                 it->setChange(Change(type));
 856                 size += it->size();
 857         }
 858
 859         writeToDestBuffer(pars);
 860
 861         if (nested_inset_level_ == 0)
 862                 compare_.progress(size);
 863 }
 864
 865
 866 void Compare::Impl::writeToDestBuffer(ParagraphList const & pars) const
 867 {
 868         pit_type const pit = dest_pars_->size() - 1;
 869         dest_pars_->insert(dest_pars_->end(), pars.begin(), pars.end());
 870         if (pit >= 0)
 871                 mergeParagraph(dest_buf_->params(), *dest_pars_, pit);
 872 }
 873
 874
 875 #include "moc_Compare.cpp"
 876
 877 } // namespace lyx