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 "Buffer.h"
  16 #include "BufferParams.h"
  17 #include "Changes.h"
  18
  19 #include "insets/InsetText.h"
  20
  21 #include "support/lassert.h"
  22
  23 #include <boost/next_prior.hpp>
  24
  25 using namespace std;
  26 using namespace lyx::support;
  27
  28
  29 namespace lyx {
  30
  31 void step_forward(DocIterator & dit)
  32 {
  33         dit.top().forwardPos();
  34 }
  35
  36
  37 void step_backward(DocIterator & dit)
  38 {
  39         dit.top().backwardPos();
  40 }
  41
  42
  43 bool step_forward(DocIterator & dit, DocIterator const & end)
  44 {
  45         if (dit == end)
  46                 return false;
  47         step_forward(dit);
  48         return true;
  49 }
  50
  51
  52 bool step_backward(DocIterator & dit, DocIterator const & beg)
  53 {
  54         if (dit == beg)
  55                 return false;
  56         step_backward(dit);
  57         return true;
  58 }
  59
  60 /**
  61  * A pair of two DocIterators that form a range.
  62  */
  63 class DocRange {
  64 public:
  65         DocRange(DocIterator from_, DocIterator to_)
  66                 : from(from_), to(to_)
  67         {}
  68
  69         DocRange(Buffer const * buf)
  70         {
  71                 from = doc_iterator_begin(buf);
  72                 to = doc_iterator_end(buf);
  73                 to.backwardPos();
  74         }
  75
  76         ///
  77         Text * text() const { return from.text(); }
  78         ///
  79         bool empty() const { return to <= from; }
  80         ///
  81         size_t length() const;
  82
  83         /// The begin of the range
  84         DocIterator from;
  85         /// The end of the range
  86         DocIterator to;
  87 };
  88
  89
  90 size_t DocRange::length() const
  91 {
  92         pit_type startpit = from.pit();
  93         pit_type endpit = to.pit();
  94         ParagraphList const & ps_ = from.text()->paragraphs();
  95
  96         ParagraphList pars(boost::next(ps_.begin(), startpit),
  97                                 boost::next(ps_.begin(), endpit + 1));
  98
  99         // Remove the end of the last paragraph; afterwards, remove the
 100         // beginning of the first paragraph.
 101         Paragraph & back = pars.back();
 102         back.eraseChars(to.pos(), back.size(), false);
 103         Paragraph & front = pars.front();
 104         front.eraseChars(0, from.pos(), false);
 105
 106         ParagraphList::const_iterator pit = pars.begin();
 107         ParagraphList::const_iterator end_it = pars.end();
 108
 109         size_t length = 0;
 110         for (; pit != end_it; ++pit)
 111                 length += pit->size() + 1;
 112
 113         // The last paragraph has no paragraph-end
 114         --length;
 115         return length;
 116 }
 117
 118
 119 class DocPair {
 120 public:
 121         DocPair() {}
 122
 123         DocPair(DocIterator o_, DocIterator n_)
 124                 : o(o_), n(n_)
 125         {}
 126
 127         DocPair & operator++()
 128         {
 129                 step_forward(o);
 130                 step_forward(n);
 131                 return *this;
 132         }
 133         ///
 134         DocIterator o;
 135         ///
 136         DocIterator n;
 137 };
 138
 139 /**
 140  * A pair of two DocRanges.
 141  */
 142 class DocRangePair {
 143 public:
 144         DocRangePair(DocRange o_, DocRange n_)
 145                 : o(o_), n(n_)
 146         {}
 147
 148         DocRangePair(DocPair from, DocPair to)
 149                 : o(from.o, to.o), n(from.n, to.n)
 150         {}
 151
 152         DocRangePair(Buffer const * o_buf, Buffer const * n_buf)
 153                 : o(o_buf), n(n_buf)
 154         {}
 155
 156         /// Returns the from pair
 157         DocPair from() const { return DocPair(o.from, n.from); }
 158
 159         /// Returns the to pair
 160         DocPair to() const { return DocPair(o.to, n.to); }
 161
 162         DocRange o;
 163         DocRange n;
 164 };
 165
 166
 167 DocRangePair stepIntoInset(DocPair const & inset_location)
 168 {
 169         DocRangePair rp(inset_location, inset_location);
 170         rp.o.from.forwardPos();
 171         rp.n.from.forwardPos();
 172         step_forward(rp.o.to);
 173         step_forward(rp.n.to);
 174         rp.o.to.backwardPos();
 175         rp.n.to.backwardPos();
 176         return rp;
 177 }
 178
 179
 180 /**
 181  * The implementation of the algorithm that does the comparison
 182  * between two documents.
 183  */
 184 class Compare::Impl {
 185 public:
 186         ///
 187         Impl(Compare const & compare)
 188                 : abort_(false), compare_(compare)
 189         {}
 190
 191         ///
 192         ~Impl() {}
 193
 194         // Algorithm to find the shortest edit string. This algorithm
 195         // only needs a linear amount of memory (linear with the sum
 196         // of the number of characters in the two paragraph-lists).
 197         bool diff(Buffer const * new_buf, Buffer const * old_buf,
 198                 Buffer const * dest_buf);
 199
 200         /// Set to true to cancel the algorithm
 201         bool abort_;
 202
 203 private:
 204         // Finds the middle snake and returns the length of the
 205         // shortest edit script.
 206         int find_middle_snake(DocRangePair const & rp, DocPair & middle_snake);
 207
 208         // This function is called recursively by a divide and conquer
 209         // algorithm. Each time, the string is divided into two split
 210         // around the middle snake.
 211         void diff_i(DocRangePair const & rp);
 212
 213         /// Processes the splitted chunks. It either adds them as deleted,
 214         /// as added, or call diff_i for further processing.
 215         void diff_part(DocRangePair const & rp);
 216
 217         /// Runs the algorithm for the inset located at /c it and /c it_n
 218         /// and adds the result to /c pars.
 219         void diff_inset(Inset * inset, DocPair const & p);
 220
 221         // Adds the snake to the destination buffer. The algorithm will
 222         // recursively be applied to any InsetTexts that are within the snake.
 223         void process_snake(DocRangePair const & rp);
 224
 225         /// Writes the range to the destination buffer
 226         void writeToDestBuffer(DocRange const & range,
 227                 Change::Type type = Change::UNCHANGED);
 228
 229         /// Writes the paragraph list to the destination buffer
 230         void writeToDestBuffer(ParagraphList const & copy_pars) const;
 231
 232         /// The length of the first chunk currently processed
 233         int N;
 234         /// The length of the second chunk currently processed
 235         int M;
 236
 237         /// The thread object, used to emit signals to the GUI
 238         Compare const & compare_;
 239
 240         /// The buffer containing text that will be marked as old
 241         Buffer const * old_buf_;
 242         /// The buffer containing text that will be marked as new
 243         Buffer const * new_buf_;
 244         /// The buffer containing text that will be marked as new
 245         Buffer const * dest_buf_;
 246
 247         /// The paragraph list of the destination buffer
 248         ParagraphList * dest_pars_;
 249
 250         /// The level of recursion
 251         int recursion_level_;
 252
 253         /// The number of nested insets at this level
 254         int nested_inset_level_;
 255 };
 256
 257 /////////////////////////////////////////////////////////////////////
 258 //
 259 // Compare
 260 //
 261 /////////////////////////////////////////////////////////////////////
 262
 263 Compare::Compare(Buffer const * new_buf, Buffer const * old_buf,
 264         Buffer * const dest_buf, CompareOptions const & options)
 265         : new_buffer(new_buf), old_buffer(old_buf), dest_buffer(dest_buf),
 266           options_(options), pimpl_(new Impl(*this))
 267 {
 268 }
 269
 270
 271 void Compare::run()
 272 {
 273         if (!dest_buffer || !new_buffer || !old_buffer)
 274                 return;
 275
 276         // Copy the buffer params to the new buffer
 277         dest_buffer->params() = options_.settings_from_new
 278                 ? new_buffer->params() : old_buffer->params();
 279
 280         // do the real work
 281         if (!doCompare())
 282                 return;
 283
 284         finished(pimpl_->abort_);
 285         return;
 286 }
 287
 288
 289 int Compare::doCompare()
 290 {
 291         return pimpl_->diff(new_buffer, old_buffer, dest_buffer);
 292 }
 293
 294
 295 void Compare::abort()
 296 {
 297         pimpl_->abort_ = true;
 298         condition_.wakeOne();
 299         wait();
 300         pimpl_->abort_ = false;
 301 }
 302
 303
 304 void get_paragraph_list(DocRange const & range,
 305         ParagraphList & pars)
 306 {
 307         // Clone the paragraphs within the selection.
 308         pit_type startpit = range.from.pit();
 309         pit_type endpit = range.to.pit();
 310         ParagraphList const & ps_ = range.text()->paragraphs();
 311         ParagraphList tmp_pars(boost::next(ps_.begin(), startpit),
 312                 boost::next(ps_.begin(), endpit + 1));
 313
 314         // Remove the end of the last paragraph; afterwards, remove the
 315         // beginning of the first paragraph. Keep this order - there may only
 316         // be one paragraph!
 317         Paragraph & back = tmp_pars.back();
 318         back.eraseChars(range.to.pos(), back.size(), false);
 319         Paragraph & front = tmp_pars.front();
 320         front.eraseChars(0, range.from.pos(), false);
 321
 322         pars.insert(pars.begin(), tmp_pars.begin(), tmp_pars.end());
 323 }
 324
 325
 326 bool equal(Inset const * i_o, Inset const * i_n)
 327 {
 328         if (!i_o || !i_n)
 329                 return false;
 330
 331         // Different types of insets
 332         if (i_o->lyxCode() != i_n->lyxCode())
 333                 return false;
 334
 335         // Editable insets are assumed to be the same as they are of the
 336         // same type. If we later on decide that we insert them in the
 337         // document as being unchanged, we will run the algorithm on the
 338         // contents of the two insets.
 339         // FIXME: This fails if the parameters of the insets differ.
 340         // FIXME: We do not recurse into InsetTabulars.
 341         // FIXME: We need methods inset->equivalent(inset).
 342         if (i_o->editable() && !i_o->asInsetMath()
 343                   && i_o->asInsetText())
 344                 return true;
 345
 346         ostringstream o_os;
 347         ostringstream n_os;
 348         i_o->write(o_os);
 349         i_n->write(n_os);
 350         return o_os.str() == n_os.str();
 351 }
 352
 353
 354 bool equal(DocIterator & o, DocIterator & n) {
 355         Paragraph const & old_par = o.text()->getPar(o.pit());
 356         Paragraph const & new_par = n.text()->getPar(n.pit());
 357
 358         Inset const * i_o = old_par.getInset(o.pos());
 359         Inset const * i_n = new_par.getInset(n.pos());
 360
 361         if (i_o && i_n)
 362                 return equal(i_o, i_n);
 363
 364         char_type c_o = old_par.getChar(o.pos());
 365         char_type c_n = new_par.getChar(n.pos());
 366         Font fo = old_par.getFontSettings(o.buffer()->params(), o.pos());
 367         Font fn = new_par.getFontSettings(n.buffer()->params(), n.pos());
 368         return c_o == c_n && fo == fn;
 369 }
 370
 371
 372 void traverse_snake_back(DocRangePair & rp)
 373 {
 374         while (true) {
 375                 // Traverse snake
 376                 if (!step_backward(rp.o.to, rp.o.from))
 377                         break;
 378
 379                 if (!step_backward(rp.n.to, rp.n.from)) {
 380                         step_forward(rp.o.to);
 381                         break;
 382                 }
 383
 384                 if (!equal(rp.o.to, rp.n.to)) {
 385                         step_forward(rp.o.to);
 386                         step_forward(rp.n.to);
 387                         break;
 388                 }
 389         }
 390 }
 391
 392
 393 void traverse_snake_forw(DocRangePair & rp)
 394 {
 395         while (equal(rp.o.from, rp.n.from)) {
 396                 if (!step_forward(rp.o.from, rp.o.to))
 397                         break;
 398
 399                 if (!step_forward(rp.n.from, rp.n.to)) {
 400                         step_backward(rp.o.from);
 401                         break;
 402                 }
 403         }
 404 }
 405
 406 /////////////////////////////////////////////////////////////////////
 407 //
 408 // Compare::Impl
 409 //
 410 /////////////////////////////////////////////////////////////////////
 411
 412 int Compare::Impl::find_middle_snake(DocRangePair const & rp,
 413         DocPair & middle_snake)
 414 {
 415         N = rp.o.length();
 416         M = rp.n.length();
 417         return M+N;
 418 }
 419
 420
 421 bool Compare::Impl::diff(Buffer const * new_buf, Buffer const * old_buf,
 422         Buffer const * dest_buf)
 423 {
 424         if (!new_buf || !old_buf || !dest_buf)
 425                 return false;
 426
 427         old_buf_ = old_buf;
 428         new_buf_ = new_buf;
 429         dest_buf_ = dest_buf;
 430         dest_pars_ = &dest_buf->inset().asInsetText()->paragraphs();
 431         dest_pars_->clear();
 432
 433         recursion_level_ = 0;
 434         nested_inset_level_ = 0;
 435
 436         DocRangePair rp(old_buf_, new_buf_);
 437
 438         DocPair from = rp.from();
 439         traverse_snake_forw(rp);
 440         DocRangePair const snake(from, rp.from());
 441         process_snake(snake);
 442
 443         // Start the recursive algorithm
 444         diff_i(rp);
 445
 446         for (pit_type p = 0; p < (pit_type)dest_pars_->size(); ++p) {
 447                 (*dest_pars_)[p].setBuffer(const_cast<Buffer &>(*dest_buf));
 448                 (*dest_pars_)[p].setInsetOwner(&dest_buf_->inset());
 449         }
 450
 451         return true;
 452 }
 453
 454
 455 void Compare::Impl::diff_i(DocRangePair const & rp)
 456 {
 457         // The middle snake
 458         DocPair middle_snake;
 459
 460         // Divides the problem into two smaller problems, split around
 461         // the snake in the middle.
 462         int const L_ses = find_middle_snake(rp, middle_snake);
 463
 464         // Set maximum of progress bar
 465         if (++recursion_level_ == 1)
 466                 compare_.progressMax(L_ses);
 467
 468         // There are now three possibilities: the strings were the same,
 469         // the strings were completely different, or we found a middle
 470         // snake and we can split the string into two parts to process.
 471         if (L_ses == 0)
 472                 // Two the same strings (this must be a very rare case, because
 473                 // usually this will be part of a snake adjacent to these strings).
 474                 writeToDestBuffer(rp.o);
 475
 476         else if (middle_snake.o.empty()) {
 477                 // Two totally different strings
 478                 writeToDestBuffer(rp.o, Change::DELETED);
 479                 writeToDestBuffer(rp.n, Change::INSERTED);
 480
 481         } else {
 482                 // Retrieve the complete snake
 483                 DocRangePair first_part(rp.from(), middle_snake);
 484                 traverse_snake_back(first_part);
 485
 486                 DocRangePair second_part(middle_snake, rp.to());
 487                 traverse_snake_forw(second_part);
 488
 489                 // Split the string in three parts:
 490                 // 1. in front of the snake
 491                 diff_part(first_part);
 492
 493                 // 2. the snake itself, and
 494                 DocRangePair const snake(first_part.to(), second_part.from());
 495                 process_snake(snake);
 496
 497                 // 3. behind the snake.
 498                 diff_part(second_part);
 499         }
 500         --recursion_level_;
 501 }
 502
 503
 504 void Compare::Impl::diff_part(DocRangePair const & rp)
 505 {
 506         // Is there a finite length string in both buffers, if not there
 507         // is an empty string and we write the other one to the buffer.
 508         if (!rp.o.empty() && !rp.n.empty())
 509                 diff_i(rp);
 510
 511         else if (!rp.o.empty())
 512                 writeToDestBuffer(rp.o, Change::DELETED);
 513
 514         else if (!rp.n.empty())
 515                 writeToDestBuffer(rp.n, Change::INSERTED);
 516 }
 517
 518
 519 void Compare::Impl::diff_inset(Inset * inset, DocPair const & p)
 520 {
 521         // Find the dociterators for the beginning and the
 522         // end of the inset, for the old and new document.
 523         DocRangePair const rp = stepIntoInset(p);
 524
 525         // Recurse into the inset. Temporarily replace the dest_pars
 526         // paragraph list by the paragraph list of the nested inset.
 527         ParagraphList * backup_dest_pars = dest_pars_;
 528         dest_pars_ = &inset->asInsetText()->text().paragraphs();
 529         dest_pars_->clear();
 530
 531         ++nested_inset_level_;
 532         diff_i(rp);
 533         --nested_inset_level_;
 534
 535         dest_pars_ = backup_dest_pars;
 536 }
 537
 538
 539 void Compare::Impl::process_snake(DocRangePair const & rp)
 540 {
 541         ParagraphList pars;
 542         get_paragraph_list(rp.o, pars);
 543
 544         // Find insets in this paragaph list
 545         DocPair it = rp.from();
 546         for (; it.o < rp.o.to; ++it) {
 547                 Inset * inset = it.o.text()->getPar(it.o.pit()).getInset(it.o.pos());
 548                 if (inset && inset->editable() && inset->asInsetText()) {
 549                         // Find the inset in the paragraph list that will be pasted into
 550                         // the final document. The contents of the inset will be replaced
 551                         // by the output of the algorithm below.
 552                         pit_type const pit = it.o.pit() - rp.o.from.pit();
 553                         pos_type const pos = pit ? it.o.pos() : it.o.pos() - rp.o.from.pos();
 554                         inset = pars[pit].getInset(pos);
 555                         LASSERT(inset, /**/);
 556                         diff_inset(inset, it);
 557                 }
 558         }
 559         writeToDestBuffer(pars);
 560 }
 561
 562
 563 void Compare::Impl::writeToDestBuffer(DocRange const & range,
 564         Change::Type type)
 565 {
 566         ParagraphList pars;
 567         get_paragraph_list(range, pars);
 568
 569         pos_type size = 0;
 570
 571         // Set the change
 572         ParagraphList::iterator it = pars.begin();
 573         for (; it != pars.end(); ++it) {
 574                 it->setChange(Change(type));
 575                 size += it->size();
 576         }
 577
 578         writeToDestBuffer(pars);
 579
 580         if (nested_inset_level_ == 0)
 581                 compare_.progress(size);
 582 }
 583
 584
 585 void Compare::Impl::writeToDestBuffer(ParagraphList const & pars) const
 586 {
 587         pit_type const pit = dest_pars_->size() - 1;
 588         dest_pars_->insert(dest_pars_->end(), pars.begin(), pars.end());
 589         if (pit >= 0)
 590                 mergeParagraph(dest_buf_->params(), *dest_pars_, pit);
 591 }
 592
 593
 594 #include "moc_Compare.cpp"
 595
 596 } // namespace lyx