X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=src%2FCompare.cpp;h=82236aa8de7f5eea7af0d69ec15d2ff8bf2b6290;hb=4ed0312c51704780af1c452d3a82a84171b3725a;hp=95eaf5abaef0f9cc1bf3eacfc89297b7348d8062;hpb=715b1303da55ef800b7ebafa26aca296f9dcffbc;p=lyx.git diff --git a/src/Compare.cpp b/src/Compare.cpp index 95eaf5abae..82236aa8de 100644 --- a/src/Compare.cpp +++ b/src/Compare.cpp @@ -12,16 +12,19 @@ #include "Compare.h" +#include "Author.h" +#include "Buffer.h" #include "BufferParams.h" #include "Changes.h" +#include "CutAndPaste.h" +#include "ErrorList.h" +#include "Font.h" #include "insets/InsetText.h" -#include "support/lassert.h" - -#include - -#include +#include "support/docstream.h" +#include "support/lassert.h" +#include "support/qstring_helpers.h" using namespace std; using namespace lyx::support; @@ -57,14 +60,14 @@ static void step(DocIterator & dit, DocIterator const & end, Direction direction */ class DocRange { public: - DocRange(DocIterator from_, DocIterator to_) + DocRange(DocIterator const & from_, DocIterator const & to_) : from(from_), to(to_) {} - DocRange(Buffer const * buf) + DocRange(Buffer const * buf) : + from(doc_iterator_begin(buf)), + to(doc_iterator_end(buf)) { - from = doc_iterator_begin(buf); - to = doc_iterator_end(buf); to.backwardPos(); } @@ -97,17 +100,19 @@ size_t DocRange::length() const class DocPair { public: - DocPair() {} + DocPair() + {} - DocPair(DocIterator o_, DocIterator n_) + DocPair(DocIterator const & o_, DocIterator const & n_) : o(o_), n(n_) {} - bool operator!=(DocPair const & rhs) { + bool operator!=(DocPair const & rhs) const + { // this might not be intuitive but correct for our purpose return o != rhs.o && n != rhs.n; } - + DocPair & operator++() { @@ -127,17 +132,17 @@ public: /// DocIterator n; }; - + /** * A pair of two DocRanges. */ class DocRangePair { public: - DocRangePair(DocRange o_, DocRange n_) + DocRangePair(DocRange const & o_, DocRange const & n_) : o(o_), n(n_) {} - - DocRangePair(DocPair from, DocPair to) + + DocRangePair(DocPair const & from, DocPair const & to) : o(from.o, to.o), n(from.n, to.n) {} @@ -146,10 +151,16 @@ public: {} /// Returns the from pair - DocPair from() const { return DocPair(o.from, n.from); } + DocPair from() const + { + return DocPair(o.from, n.from); + } /// Returns the to pair - DocPair to() const { return DocPair(o.to, n.to); } + DocPair to() const + { + return DocPair(o.to, n.to); + } DocRange o; DocRange n; @@ -181,7 +192,8 @@ static DocRangePair stepIntoInset(DocPair const & inset_location) template class compl_vector { public: - compl_vector() {} + compl_vector() + {} void reset(T const & def) { @@ -218,14 +230,18 @@ private: class Compare::Impl { public: /// - Impl(Compare const & compare) - : abort_(false), compare_(compare) + Impl(Compare const & compare) + : abort_(false), n_(0), m_(0), offset_reverse_diagonal_(0), + odd_offset_(false), compare_(compare), + old_buf_(nullptr), new_buf_(nullptr), dest_buf_(nullptr), + dest_pars_(nullptr), recursion_level_(0), nested_inset_level_(0), D_(0) {} /// - ~Impl() {} + ~Impl() + {} - // Algorithm to find the shortest edit string. This algorithm + // Algorithm to find the shortest edit string. This algorithm // only needs a linear amount of memory (linear with the sum // of the number of characters in the two paragraph-lists). bool diff(Buffer const * new_buf, Buffer const * old_buf, @@ -234,10 +250,19 @@ public: /// Set to true to cancel the algorithm bool abort_; + /// + QString status() + { + QString status; + status += toqstr("recursion level:") + " " + QString::number(recursion_level_) + + " " + toqstr("differences:") + " " + QString::number(D_); + return status; + } + private: /// Finds the middle snake and returns the length of the /// shortest edit script. - int find_middle_snake(DocRangePair const & rp, DocPair & middle_snake); + int findMiddleSnake(DocRangePair const & rp, DocPair & middle_snake); enum SnakeResult { NoSnake, @@ -247,46 +272,46 @@ private: /// Retrieve the middle snake when there is overlap between /// the forward and backward path. - SnakeResult retrieve_middle_snake(int k, int D, Direction direction, + SnakeResult retrieveMiddleSnake(int k, int D, Direction direction, DocPair & middle_snake); - - /// Find the the furthest reaching D-path (number of horizontal + + /// Find the furthest reaching D-path (number of horizontal /// and vertical steps; differences between the old and new /// document) in the k-diagonal (vertical minus horizontal steps). - void furthest_Dpath_kdiagonal(int D, int k, + void furthestDpathKdiagonal(int D, int k, DocRangePair const & rp, Direction direction); /// Is there overlap between the forward and backward path bool overlap(int k, int D); - + /// This function is called recursively by a divide and conquer /// algorithm. Each time, the string is divided into two split /// around the middle snake. void diff_i(DocRangePair const & rp); - /// Processes the splitted chunks. It either adds them as deleted, + /// Processes the split chunks. It either adds them as deleted, /// as added, or call diff_i for further processing. - void diff_part(DocRangePair const & rp); + void diffPart(DocRangePair const & rp); - /// Runs the algorithm for the inset located at /c it and /c it_n + /// Runs the algorithm for the inset located at /c it and /c it_n /// and adds the result to /c pars. - void diff_inset(Inset * inset, DocPair const & p); + void diffInset(Inset * inset, DocPair const & p); /// Adds the snake to the destination buffer. The algorithm will /// recursively be applied to any InsetTexts that are within the snake. - void process_snake(DocRangePair const & rp); + void processSnake(DocRangePair const & rp); /// Writes the range to the destination buffer void writeToDestBuffer(DocRange const & range, Change::Type type = Change::UNCHANGED); - + /// Writes the paragraph list to the destination buffer void writeToDestBuffer(ParagraphList const & copy_pars) const; /// The length of the old chunk currently processed - int N_; + int n_; /// The length of the new chunk currently processed - int M_; + int m_; /// The offset diagonal of the reverse path of the /// currently processed chunk int offset_reverse_diagonal_; @@ -322,6 +347,10 @@ private: compl_vector nrp; compl_vector ors; compl_vector nrs; + + /// The number of differences in the path the algorithm + /// is currently processing. + int D_; }; ///////////////////////////////////////////////////////////////////// @@ -335,6 +364,15 @@ Compare::Compare(Buffer const * new_buf, Buffer const * old_buf, : new_buffer(new_buf), old_buffer(old_buf), dest_buffer(dest_buf), options_(options), pimpl_(new Impl(*this)) { + connect(&status_timer_, SIGNAL(timeout()), + this, SLOT(doStatusMessage())); + status_timer_.start(1000); +} + + +void Compare::doStatusMessage() +{ + statusMessage(pimpl_->status()); } @@ -343,16 +381,37 @@ void Compare::run() if (!dest_buffer || !new_buffer || !old_buffer) return; - // Copy the buffer params to the new buffer + // Copy the buffer params to the destination buffer dest_buffer->params() = options_.settings_from_new ? new_buffer->params() : old_buffer->params(); - - // do the real work + // Copy extra authors to the destination buffer + AuthorList const & extra_authors = options_.settings_from_new ? + old_buffer->params().authors() : new_buffer->params().authors(); + AuthorList::Authors::const_iterator it = extra_authors.begin(); + for (; it != extra_authors.end(); ++it) + dest_buffer->params().authors().record(*it); + + // We will need this later + DocumentClassConstPtr const olddc = + dest_buffer->params().documentClassPtr(); + // We do not want to share the DocumentClass with the other Buffer. + // See bug #10295. + dest_buffer->params().makeDocumentClass(dest_buffer->isClone(), dest_buffer->isInternal()); + + doStatusMessage(); + // Do the real work if (!doCompare()) return; - + + // The comparison routine simply copies the paragraphs over into the + // new buffer with the document class from wherever they came from. + // So we need to reset the document class of all the paragraphs. + // See bug #10295. + cap::switchBetweenClasses( + olddc, dest_buffer->params().documentClassPtr(), + static_cast(dest_buffer->inset())); + finished(pimpl_->abort_); - return; } @@ -371,15 +430,15 @@ void Compare::abort() } -static void get_paragraph_list(DocRange const & range, +static void getParagraphList(DocRange const & range, ParagraphList & pars) { // Clone the paragraphs within the selection. pit_type startpit = range.from.pit(); pit_type endpit = range.to.pit(); ParagraphList const & ps_ = range.text()->paragraphs(); - ParagraphList tmp_pars(boost::next(ps_.begin(), startpit), - boost::next(ps_.begin(), endpit + 1)); + ParagraphList tmp_pars(ps_.iterator_at(startpit), + ps_.iterator_at(endpit + 1)); // Remove the end of the last paragraph; afterwards, remove the // beginning of the first paragraph. Keep this order - there may only @@ -402,7 +461,7 @@ static bool equal(Inset const * i_o, Inset const * i_n) if (i_o->lyxCode() != i_n->lyxCode()) return false; - // Editable insets are assumed to be the same as they are of the + // Editable insets are assumed to be the same as they are of the // same type. If we later on decide that we insert them in the // document as being unchanged, we will run the algorithm on the // contents of the two insets. @@ -421,7 +480,15 @@ static bool equal(Inset const * i_o, Inset const * i_n) } -static bool equal(DocIterator & o, DocIterator & n) { +static bool equal(DocIterator & o, DocIterator & n) +{ + // Explicitly check for this, so we won't call + // Paragraph::getChar for the last pos. + bool const o_lastpos = o.pos() == o.lastpos(); + bool const n_lastpos = n.pos() == n.lastpos(); + if (o_lastpos || n_lastpos) + return o_lastpos && n_lastpos; + Paragraph const & old_par = o.text()->getPar(o.pit()); Paragraph const & new_par = n.text()->getPar(n.pit()); @@ -436,7 +503,7 @@ static bool equal(DocIterator & o, DocIterator & n) { if (i_o && i_n) return equal(i_o, i_n); - } + } Font fo = old_par.getFontSettings(o.buffer()->params(), o.pos()); Font fn = new_par.getFontSettings(n.buffer()->params(), n.pos()); @@ -444,15 +511,15 @@ static bool equal(DocIterator & o, DocIterator & n) { } -/// Traverses a snake in a certain direction. p points to a +/// Traverses a snake in a certain direction. p points to a /// position in the old and new file and they are synchronously /// moved along the snake. The function returns true if a snake /// was found. -static bool traverse_snake(DocPair & p, DocRangePair const & range, +static bool traverseSnake(DocPair & p, DocRangePair const & range, Direction direction) { bool ret = false; - DocPair const & p_end = + DocPair const & p_end = direction == Forward ? range.to() : range.from(); while (p != p_end) { @@ -478,7 +545,7 @@ static bool traverse_snake(DocPair & p, DocRangePair const & range, ///////////////////////////////////////////////////////////////////// -void Compare::Impl::furthest_Dpath_kdiagonal(int D, int k, +void Compare::Impl::furthestDpathKdiagonal(int D, int k, DocRangePair const & rp, Direction direction) { compl_vector & op = direction == Forward ? ofp : orp; @@ -496,6 +563,7 @@ void Compare::Impl::furthest_Dpath_kdiagonal(int D, int k, // Where do we take the step from ? int const kk = vertical_step ? k + 1 : k - 1; DocPair p(op[kk], np[kk]); + DocPair const s(os[kk], ns[kk]); // If D==0 we simulate a vertical step from (0,-1) by doing nothing. if (D != 0) { @@ -508,17 +576,17 @@ void Compare::Impl::furthest_Dpath_kdiagonal(int D, int k, step(p.o, rp.o.to, direction); else if (!vertical_step && direction == Backward) step(p.o, rp.o.from, direction); - } - + } + // Traverse snake - if (traverse_snake(p, rp, direction)) { + if (traverseSnake(p, rp, direction)) { // Record last snake os[k] = p.o; ns[k] = p.n; } else { // Copy last snake from the previous step - os[k] = os[kk]; - ns[k] = ns[kk]; + os[k] = s.o; + ns[k] = s.n; } //Record new position @@ -544,7 +612,7 @@ bool Compare::Impl::overlap(int k, int D) } -Compare::Impl::SnakeResult Compare::Impl::retrieve_middle_snake( +Compare::Impl::SnakeResult Compare::Impl::retrieveMiddleSnake( int k, int D, Direction direction, DocPair & middle_snake) { compl_vector & os = direction == Forward ? ofs : ors; @@ -559,10 +627,10 @@ Compare::Impl::SnakeResult Compare::Impl::retrieve_middle_snake( if (os[k].empty() && os_r[kk].empty()) { // No, there is no snake at all, in which case // the length of the shortest edit script is M+N. - LASSERT(2 * D - odd_offset_ == M_ + N_, /**/); + LATTEST(2 * D - odd_offset_ == m_ + n_); return NoSnake; - } - + } + if (os[k].empty()) { // Yes, but there is only 1 snake and we found it in the // reverse path. @@ -577,16 +645,16 @@ Compare::Impl::SnakeResult Compare::Impl::retrieve_middle_snake( } -int Compare::Impl::find_middle_snake(DocRangePair const & rp, +int Compare::Impl::findMiddleSnake(DocRangePair const & rp, DocPair & middle_snake) { // The lengths of the old and new chunks. - N_ = rp.o.length(); - M_ = rp.n.length(); + n_ = rp.o.length(); + m_ = rp.n.length(); // Forward paths are centered around the 0-diagonal; reverse paths // are centered around the diagonal N - M. (Delta in the article) - offset_reverse_diagonal_ = N_ - M_; + offset_reverse_diagonal_ = n_ - m_; // If the offset is odd, only check for overlap while extending forward // paths, otherwise only check while extending reverse paths. @@ -601,19 +669,22 @@ int Compare::Impl::find_middle_snake(DocRangePair const & rp, ors.reset(DocIterator()); nrs.reset(DocIterator()); + // In the formula below, the "+ 1" ensures we round like ceil() + int const D_max = (m_ + n_ + 1)/2; // D is the number of horizontal and vertical steps, i.e. // different characters in the old and new chunk. - int const D_max = ceil(((double)M_ + N_)/2); for (int D = 0; D <= D_max; ++D) { + // to be used in the status messages + D_ = D; // Forward and reverse paths for (int f = 0; f < 2; ++f) { Direction direction = f == 0 ? Forward : Backward; // Diagonals between -D and D can be reached by a D-path - for (int k = -D; k <= D; k += 2) { + for (int k = -D; k <= D; k += 2) { // Find the furthest reaching D-path on this diagonal - furthest_Dpath_kdiagonal(D, k, rp, direction); + furthestDpathKdiagonal(D, k, rp, direction); // Only check for overlap for forward paths if the offset is odd // and only for reverse paths if the offset is even. @@ -621,10 +692,12 @@ int Compare::Impl::find_middle_snake(DocRangePair const & rp, // Do the forward and backward paths overlap ? if (overlap(k, D - odd_offset_)) { - retrieve_middle_snake(k, D, direction, middle_snake); + retrieveMiddleSnake(k, D, direction, middle_snake); return 2 * D - odd_offset_; } } + if (abort_) + return 0; } } } @@ -651,15 +724,17 @@ bool Compare::Impl::diff(Buffer const * new_buf, Buffer const * old_buf, DocRangePair rp(old_buf_, new_buf_); DocPair from = rp.from(); - traverse_snake(from, rp, Forward); + traverseSnake(from, rp, Forward); DocRangePair const snake(rp.from(), from); - process_snake(snake); - + processSnake(snake); + // Start the recursive algorithm - diff_i(rp); + DocRangePair rp_new(from, rp.to()); + if (!rp_new.o.empty() || !rp_new.n.empty()) + diff_i(rp_new); for (pit_type p = 0; p < (pit_type)dest_pars_->size(); ++p) { - (*dest_pars_)[p].setBuffer(const_cast(*dest_buf)); + (*dest_pars_)[p].setInsetBuffers(const_cast(*dest_buf)); (*dest_pars_)[p].setInsetOwner(&dest_buf_->inset()); } @@ -669,12 +744,15 @@ bool Compare::Impl::diff(Buffer const * new_buf, Buffer const * old_buf, void Compare::Impl::diff_i(DocRangePair const & rp) { + if (abort_) + return; + // The middle snake DocPair middle_snake; // Divides the problem into two smaller problems, split around // the snake in the middle. - int const L_ses = find_middle_snake(rp, middle_snake); + int const L_ses = findMiddleSnake(rp, middle_snake); // Set maximum of progress bar if (++recursion_level_ == 1) @@ -696,35 +774,35 @@ void Compare::Impl::diff_i(DocRangePair const & rp) } else { // Retrieve the complete snake DocPair first_part_end = middle_snake; - traverse_snake(first_part_end, rp, Backward); + traverseSnake(first_part_end, rp, Backward); DocRangePair first_part(rp.from(), first_part_end); - + DocPair second_part_begin = middle_snake; - traverse_snake(second_part_begin, rp, Forward); + traverseSnake(second_part_begin, rp, Forward); DocRangePair second_part(second_part_begin, rp.to()); - + // Split the string in three parts: // 1. in front of the snake - diff_part(first_part); + diffPart(first_part); // 2. the snake itself, and DocRangePair const snake(first_part.to(), second_part.from()); - process_snake(snake); + processSnake(snake); // 3. behind the snake. - diff_part(second_part); + diffPart(second_part); } --recursion_level_; } -void Compare::Impl::diff_part(DocRangePair const & rp) +void Compare::Impl::diffPart(DocRangePair const & rp) { // Is there a finite length string in both buffers, if not there // is an empty string and we write the other one to the buffer. if (!rp.o.empty() && !rp.n.empty()) diff_i(rp); - + else if (!rp.o.empty()) writeToDestBuffer(rp.o, Change::DELETED); @@ -733,7 +811,7 @@ void Compare::Impl::diff_part(DocRangePair const & rp) } -void Compare::Impl::diff_inset(Inset * inset, DocPair const & p) +void Compare::Impl::diffInset(Inset * inset, DocPair const & p) { // Find the dociterators for the beginning and the // end of the inset, for the old and new document. @@ -744,7 +822,7 @@ void Compare::Impl::diff_inset(Inset * inset, DocPair const & p) ParagraphList * backup_dest_pars = dest_pars_; dest_pars_ = &inset->asInsetText()->text().paragraphs(); dest_pars_->clear(); - + ++nested_inset_level_; diff_i(rp); --nested_inset_level_; @@ -753,10 +831,10 @@ void Compare::Impl::diff_inset(Inset * inset, DocPair const & p) } -void Compare::Impl::process_snake(DocRangePair const & rp) +void Compare::Impl::processSnake(DocRangePair const & rp) { ParagraphList pars; - get_paragraph_list(rp.o, pars); + getParagraphList(rp.o, pars); // Find insets in this paragaph list DocPair it = rp.from(); @@ -769,8 +847,8 @@ void Compare::Impl::process_snake(DocRangePair const & rp) pit_type const pit = it.o.pit() - rp.o.from.pit(); pos_type const pos = pit ? it.o.pos() : it.o.pos() - rp.o.from.pos(); inset = pars[pit].getInset(pos); - LASSERT(inset, /**/); - diff_inset(inset, it); + LASSERT(inset, continue); + diffInset(inset, it); } } writeToDestBuffer(pars); @@ -781,14 +859,14 @@ void Compare::Impl::writeToDestBuffer(DocRange const & range, Change::Type type) { ParagraphList pars; - get_paragraph_list(range, pars); + getParagraphList(range, pars); pos_type size = 0; // Set the change ParagraphList::iterator it = pars.begin(); for (; it != pars.end(); ++it) { - it->setChange(Change(type)); + it->setChange(Change(type, compare_.options_.author)); size += it->size(); }