X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=src%2FCompare.cpp;h=5831f2211114ef6c78e7a313f9e4d3dd1c2958cb;hb=f08f5821ec5d29232bccb342a5b1ff86600b0716;hp=db849b1bd229bc6a04e7faa11450d604316fe692;hpb=43c8de81388ffa0c7f0530bedb14ac3b9ed82e1e;p=lyx.git diff --git a/src/Compare.cpp b/src/Compare.cpp index db849b1bd2..5831f22111 100644 --- a/src/Compare.cpp +++ b/src/Compare.cpp @@ -14,15 +14,15 @@ #include "BufferParams.h" #include "Changes.h" +#include "Font.h" #include "insets/InsetText.h" #include "support/lassert.h" +#include "support/qstring_helpers.h" #include -#include - using namespace std; using namespace lyx::support; @@ -84,42 +84,28 @@ public: size_t DocRange::length() const { - pit_type startpit = from.pit(); - pit_type endpit = to.pit(); - ParagraphList const & ps_ = from.text()->paragraphs(); - - ParagraphList pars(boost::next(ps_.begin(), startpit), - boost::next(ps_.begin(), endpit + 1)); - - // Remove the end of the last paragraph; afterwards, remove the - // beginning of the first paragraph. - Paragraph & back = pars.back(); - back.eraseChars(to.pos(), back.size(), false); - Paragraph & front = pars.front(); - front.eraseChars(0, from.pos(), false); - - ParagraphList::const_iterator pit = pars.begin(); - ParagraphList::const_iterator end_it = pars.end(); - + ParagraphList const & ps = from.text()->paragraphs(); size_t length = 0; - for (; pit != end_it; ++pit) - length += pit->size() + 1; - - // The last paragraph has no paragraph-end - --length; - return length; + pit_type pit = from.pit(); + pit_type const endpit = to.pit(); + for (; pit < endpit; ++pit) + length += ps[pit].size() + 1; + length += to.pos() - from.pos(); + return length; } class DocPair { public: - DocPair() {} + DocPair() + {} DocPair(DocIterator o_, DocIterator n_) : o(o_), n(n_) {} - bool operator!=(DocPair const & rhs) { + bool operator!=(DocPair const & rhs) + { // this might not be intuitive but correct for our purpose return o != rhs.o && n != rhs.n; } @@ -162,10 +148,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; @@ -197,7 +189,8 @@ static DocRangePair stepIntoInset(DocPair const & inset_location) template class compl_vector { public: - compl_vector() {} + compl_vector() + {} void reset(T const & def) { @@ -206,36 +199,14 @@ public: Vn_.clear(); } - /// Gets the value at index. If it is not in the vector - /// the default value is returned. - T & get(int index) { - if (-index <= int(Vn_.size()) && index < int(Vp_.size())) - return index >= 0 ? Vp_[index] : Vn_[-index-1]; - else - return default_; - } - - /// Sets the value at index if it already - /// is in the vector. Otherwise it will be added to the - /// end padded with the default value. - void set(int index, T const & t) { - if (index >= -int(Vn_.size()) && index < int(Vp_.size())) { - if (index >= 0) - Vp_[index] = t; - else - Vn_[-index-1] = t; - } else { - while (index > int(Vp_.size())) - Vp_.push_back(default_); - while (index < -int(Vn_.size()) - 1) - Vn_.push_back(default_); - - if (index >= 0) - Vp_.push_back(t); - else - Vn_.push_back(t); - } + /// the default value is inserted and returned. + T & operator[](int index) { + vector & V = index >= 0 ? Vp_ : Vn_; + unsigned int const ii = index >= 0 ? index : -index - 1; + while (ii >= V.size()) + V.push_back(default_); + return V[ii]; } private: @@ -257,11 +228,12 @@ class Compare::Impl { public: /// Impl(Compare const & compare) - : abort_(false), compare_(compare) + : abort_(false), compare_(compare), recursion_level_(0), D_(0) {} /// - ~Impl() {} + ~Impl() + {} // Algorithm to find the shortest edit string. This algorithm // only needs a linear amount of memory (linear with the sum @@ -272,10 +244,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, @@ -285,13 +266,13 @@ 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 /// 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 @@ -302,17 +283,17 @@ private: /// 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 /// 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, @@ -360,6 +341,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_; }; ///////////////////////////////////////////////////////////////////// @@ -373,6 +358,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()); } @@ -385,6 +379,8 @@ void Compare::run() dest_buffer->params() = options_.settings_from_new ? new_buffer->params() : old_buffer->params(); + doStatusMessage(); + // do the real work if (!doCompare()) return; @@ -409,7 +405,7 @@ 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. @@ -459,7 +455,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()); @@ -486,7 +490,7 @@ static bool equal(DocIterator & o, DocIterator & n) { /// 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; @@ -516,25 +520,25 @@ 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; - compl_vector * np = direction == Forward ? &nfp : &nrp; - compl_vector * os = direction == Forward ? &ofs : &ors; - compl_vector * ns = direction == Forward ? &nfs : &nrs; + compl_vector & op = direction == Forward ? ofp : orp; + compl_vector & np = direction == Forward ? nfp : nrp; + compl_vector & os = direction == Forward ? ofs : ors; + compl_vector & ns = direction == Forward ? nfs : nrs; // A vertical step means stepping one character in the new document. bool vertical_step = k == -D; if (!vertical_step && k != D) { vertical_step = direction == Forward - ? op->get(k - 1) < op->get(k + 1) - : op->get(k - 1) > op->get(k + 1); + ? op[k - 1] < op[k + 1] : op[k - 1] > op[k + 1]; } // Where do we take the step from ? int const kk = vertical_step ? k + 1 : k - 1; - DocPair p(op->get(kk), np->get(kk)); + 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) { @@ -550,19 +554,19 @@ void Compare::Impl::furthest_Dpath_kdiagonal(int D, int k, } // Traverse snake - if (traverse_snake(p, rp, direction)) { + if (traverseSnake(p, rp, direction)) { // Record last snake - os->set(k, p.o); - ns->set(k, p.n); + os[k] = p.o; + ns[k] = p.n; } else { // Copy last snake from the previous step - os->set(k, os->get(kk)); - ns->set(k, ns->get(kk)); + os[k] = s.o; + ns[k] = s.n; } //Record new position - op->set(k, p.o); - np->set(k, p.n); + op[k] = p.o; + np[k] = p.n; } @@ -575,48 +579,48 @@ bool Compare::Impl::overlap(int k, int D) if (kk <= D && kk >= -D) { // Do we have overlap ? if (odd_offset_) - return ofp.get(k) >= orp.get(kk) && nfp.get(k) >= nrp.get(kk); + return ofp[k] >= orp[kk] && nfp[k] >= nrp[kk]; else - return ofp.get(kk) >= orp.get(k) && nfp.get(kk) >= nrp.get(k); + return ofp[kk] >= orp[k] && nfp[kk] >= nrp[k]; } return false; } -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; - compl_vector * ns = direction == Forward ? &nfs : &nrs; - compl_vector * os_r = direction == Forward ? &ors : &ofs; - compl_vector * ns_r = direction == Forward ? &nrs : &nfs; + compl_vector & os = direction == Forward ? ofs : ors; + compl_vector & ns = direction == Forward ? nfs : nrs; + compl_vector & os_r = direction == Forward ? ors : ofs; + compl_vector & ns_r = direction == Forward ? nrs : nfs; // The diagonal while doing the backward search int kk = -k + offset_reverse_diagonal_; // Did we find a snake ? - if (os->get(k).empty() && os_r->get(kk).empty()) { + 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_, /**/); return NoSnake; } - if (os->get(k).empty()) { + if (os[k].empty()) { // Yes, but there is only 1 snake and we found it in the // reverse path. - middle_snake.o = os_r->get(kk); - middle_snake.n = ns_r->get(kk); + middle_snake.o = os_r[kk]; + middle_snake.n = ns_r[kk]; return SingleSnake; } - middle_snake.o = os->get(k); - middle_snake.n = ns->get(k); + middle_snake.o = os[k]; + middle_snake.n = ns[k]; return NormalSnake; } -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. @@ -640,10 +644,13 @@ 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) { @@ -652,7 +659,7 @@ int Compare::Impl::find_middle_snake(DocRangePair const & rp, // Diagonals between -D and D can be reached by a D-path 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. @@ -660,10 +667,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; } } } @@ -690,12 +699,14 @@ 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)); @@ -708,12 +719,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) @@ -735,29 +749,29 @@ 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. @@ -772,7 +786,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. @@ -792,10 +806,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(); @@ -809,7 +823,7 @@ void Compare::Impl::process_snake(DocRangePair const & rp) 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); + diffInset(inset, it); } } writeToDestBuffer(pars); @@ -820,7 +834,7 @@ void Compare::Impl::writeToDestBuffer(DocRange const & range, Change::Type type) { ParagraphList pars; - get_paragraph_list(range, pars); + getParagraphList(range, pars); pos_type size = 0;