src/Undo.cpp

   1 /**
   2  * \file Undo.cpp
   3  * This file is part of LyX, the document processor.
   4  * Licence details can be found in the file COPYING.
   5  *
   6  * \author Asger Alstrup
   7  * \author Lars Gullik Bjønnes
   8  * \author John Levon
   9  * \author André Pönitz
  10  * \author Jürgen Vigna
  11  * \author Abdelrazak Younes
  12  *
  13  * Full author contact details are available in file CREDITS.
  14  */
  15
  16 #include <config.h>
  17
  18 #include "Undo.h"
  19
  20 #include "Buffer.h"
  21 #include "BufferList.h"
  22 #include "BufferParams.h"
  23 #include "Cursor.h"
  24 #include "CutAndPaste.h"
  25 #include "ErrorList.h"
  26 #include "Paragraph.h"
  27 #include "ParagraphList.h"
  28 #include "Text.h"
  29
  30 #include "mathed/InsetMath.h"
  31 #include "mathed/MathData.h"
  32 #include "mathed/MathRow.h"
  33
  34 #include "insets/InsetText.h"
  35
  36 #include "support/debug.h"
  37 #include "support/lassert.h"
  38 #include "support/lyxtime.h"
  39
  40 #include <algorithm>
  41 #include <deque>
  42 #include <set>
  43
  44 using namespace std;
  45 using namespace lyx::support;
  46
  47
  48 namespace lyx {
  49
  50 /**
  51 These are the elements put on the undo stack. Each object contains
  52 complete paragraphs from some cell and sufficient information to
  53 restore the cursor state.
  54
  55 The cell is given by a DocIterator pointing to this cell, the
  56 'interesting' range of paragraphs by counting them from begin and end
  57 of cell, respectively.
  58
  59 The cursor is also given as DocIterator and should point to some place
  60 in the stored paragraph range. In case of math, we simply store the
  61 whole cell, as there usually is just a simple paragraph in a cell.
  62
  63 The idea is to store the contents of 'interesting' paragraphs in some
  64 structure ('Undo') _before_ it is changed in some edit operation.
  65 Obviously, the stored range should be as small as possible. However,
  66 there is a lower limit: The StableDocIterator stored in the undo class
  67 must be valid after the changes, too, as it will used as a pointer
  68 where to insert the stored bits when performining undo.
  69 */
  70 struct UndoElement
  71 {
  72         ///
  73         UndoElement(UndoKind kin, CursorData const & cb,
  74                     StableDocIterator const & cel,
  75                     pit_type fro, pit_type en, ParagraphList * pl, MathData * ar,
  76                     bool lc, size_t gid) :
  77                 cur_before(cb), cell(cel), from(fro), end(en),
  78                 pars(pl), array(ar), bparams(nullptr),
  79                 group_id(gid), time(current_time()), kind(kin), lyx_clean(lc)
  80                 {}
  81         ///
  82         UndoElement(CursorData const & cb, BufferParams const & bp,
  83                                 bool lc, size_t gid) :
  84                 cur_before(cb), cell(), from(0), end(0),
  85                 pars(nullptr), array(nullptr), bparams(new BufferParams(bp)),
  86                 group_id(gid), time(current_time()), kind(ATOMIC_UNDO), lyx_clean(lc)
  87         {}
  88         ///
  89         UndoElement(UndoElement const & ue) :
  90                 cur_before(ue.cur_before), cur_after(ue.cur_after),
  91                 cell(ue.cell), from(ue.from), end(ue.end),
  92                 pars(ue.pars), array(ue.array),
  93                 bparams(ue.bparams ? new BufferParams(*ue.bparams) : nullptr),
  94                 group_id(ue.group_id), time(current_time()), kind(ue.kind),
  95                 lyx_clean(ue.lyx_clean)
  96                 {}
  97         ///
  98         ~UndoElement()
  99         {
 100                 if (bparams)
 101                         delete bparams;
 102         }
 103         /// the position of the cursor before recordUndo
 104         CursorData cur_before;
 105         /// the position of the cursor at the end of the undo group
 106         CursorData cur_after;
 107         /// the position of the cell described
 108         StableDocIterator cell;
 109         /// counted from begin of cell
 110         pit_type from;
 111         /// complement to end of this cell
 112         pit_type end;
 113         /// the contents of the saved Paragraphs (for texted)
 114         ParagraphList * pars;
 115         /// the contents of the saved MathData (for mathed)
 116         MathData * array;
 117         /// Only used in case of params undo
 118         BufferParams const * bparams;
 119         /// the element's group id
 120         size_t group_id;
 121         /// timestamp
 122         time_t time;
 123         /// Which kind of operation are we recording for?
 124         UndoKind kind;
 125         /// Was the buffer clean at this point?
 126         bool lyx_clean;
 127 private:
 128         /// Protect construction
 129         UndoElement();
 130 };
 131
 132
 133 class UndoElementStack
 134 {
 135 public:
 136         /// limit is the maximum size of the stack
 137         UndoElementStack(size_t limit = 100) { limit_ = limit; }
 138         /// limit is the maximum size of the stack
 139         ~UndoElementStack() { clear(); }
 140
 141         /// Return the top element.
 142         UndoElement & top() { return c_.front(); }
 143
 144         /// Pop and throw away the top element.
 145         void pop() { c_.pop_front(); }
 146
 147         /// Return true if the stack is empty.
 148         bool empty() const { return c_.empty(); }
 149
 150         /// Clear all elements, deleting them.
 151         void clear() {
 152                 for (size_t i = 0; i != c_.size(); ++i) {
 153                         delete c_[i].array;
 154                         delete c_[i].pars;
 155                 }
 156                 c_.clear();
 157         }
 158
 159         /// Push an item on to the stack, deleting the bottom group on
 160         /// overflow.
 161         void push(UndoElement const & v) {
 162                 // Remove some entries if the limit has been reached.
 163                 // However, if the only group on the stack is the one
 164                 // we are currently populating, do nothing.
 165                 if (c_.size() >= limit_
 166                     && c_.front().group_id != v.group_id) {
 167                         // remove a whole group at once.
 168                         const size_t gid = c_.back().group_id;
 169                         while (!c_.empty() && c_.back().group_id == gid)
 170                                 c_.pop_back();
 171                 }
 172                 c_.push_front(v);
 173         }
 174
 175         /// Mark all the elements of the stack as dirty
 176         void markDirty() {
 177                 for (size_t i = 0; i != c_.size(); ++i)
 178                         c_[i].lyx_clean = false;
 179         }
 180
 181 private:
 182         /// Internal contents.
 183         std::deque<UndoElement> c_;
 184         /// The maximum number elements stored.
 185         size_t limit_;
 186 };
 187
 188
 189 struct Undo::Private
 190 {
 191         Private(Buffer & buffer) : buffer_(buffer),
 192                 group_id_(0), group_level_(0), undo_finished_(true) {}
 193
 194         // Do one undo/redo step
 195         void doUndoRedoAction(CursorData & cur, UndoElementStack & stack,
 196                               UndoElementStack & otherStack);
 197         // Apply one undo/redo group. Returns false if no undo possible.
 198         bool undoRedoAction(CursorData & cur, bool isUndoOperation);
 199
 200         ///
 201         void doRecordUndo(UndoKind kind,
 202                 DocIterator const & cell,
 203                 pit_type first_pit,
 204                 pit_type last_pit,
 205                 CursorData const & cur,
 206                 UndoElementStack & stack);
 207         ///
 208         void recordUndo(UndoKind kind,
 209                 DocIterator const & cell,
 210                 pit_type first_pit,
 211                 pit_type last_pit,
 212                 CursorData const & cur);
 213         ///
 214         void doRecordUndoBufferParams(CursorData const & cur, UndoElementStack & stack);
 215         ///
 216         void recordUndoBufferParams(CursorData const & cur);
 217
 218         ///
 219         Buffer & buffer_;
 220         /// Undo stack.
 221         UndoElementStack undostack_;
 222         /// Redo stack.
 223         UndoElementStack redostack_;
 224
 225         /// Current group Id.
 226         size_t group_id_;
 227         /// Current group nesting nevel.
 228         size_t group_level_;
 229         /// the position of cursor before the group was created
 230         CursorData group_cur_before_;
 231
 232         /// The flag used by Undo::finishUndo().
 233         bool undo_finished_;
 234
 235 };
 236
 237
 238 /////////////////////////////////////////////////////////////////////
 239 //
 240 // Undo
 241 //
 242 /////////////////////////////////////////////////////////////////////
 243
 244
 245 Undo::Undo(Buffer & buffer)
 246         : d(new Undo::Private(buffer))
 247 {}
 248
 249
 250 Undo::~Undo()
 251 {
 252         delete d;
 253 }
 254
 255
 256 void Undo::clear()
 257 {
 258         d->undostack_.clear();
 259         d->redostack_.clear();
 260         d->undo_finished_ = true;
 261         // We used to do that, but I believe it is better to keep
 262         // groups (only used in Buffer::reload for now (JMarc)
 263         //d->group_id_ = 0;
 264         //d->group_level_ = 0;
 265 }
 266
 267
 268 bool Undo::hasUndoStack() const
 269 {
 270         return !d->undostack_.empty();
 271 }
 272
 273
 274 bool Undo::hasRedoStack() const
 275 {
 276         return !d->redostack_.empty();
 277 }
 278
 279
 280 void Undo::markDirty()
 281 {
 282         d->undo_finished_ = true;
 283         d->undostack_.markDirty();
 284         d->redostack_.markDirty();
 285 }
 286
 287
 288 /////////////////////////////////////////////////////////////////////
 289 //
 290 // Undo::Private
 291 //
 292 ///////////////////////////////////////////////////////////////////////
 293
 294 static bool samePar(StableDocIterator const & i1, StableDocIterator const & i2)
 295 {
 296         StableDocIterator tmpi2 = i2;
 297         tmpi2.pos() = i1.pos();
 298         return i1 == tmpi2;
 299 }
 300
 301
 302 void Undo::Private::doRecordUndo(UndoKind kind,
 303         DocIterator const & cell,
 304         pit_type first_pit, pit_type last_pit,
 305         CursorData const & cur_before,
 306         UndoElementStack & stack)
 307 {
 308         if (!group_level_) {
 309                 LYXERR0("There is no group open (creating one)");
 310                 ++group_id_;
 311         }
 312
 313         if (first_pit > last_pit)
 314                 swap(first_pit, last_pit);
 315         pit_type const from = first_pit;
 316         pit_type const end = cell.lastpit() - last_pit;
 317
 318         /* Undo coalescing: if the undo element we want to add only
 319          * changes stuff that was already modified by the previous one on
 320          * undo stack (in the same group), then skip it. There is nothing
 321          * to gain in adding it to the stack. The code below works for
 322          * both texted and mathed.
 323         */
 324         if (!stack.empty()
 325             && stack.top().group_id == group_id_
 326             && !stack.top().bparams
 327             && samePar(stack.top().cell, cell)
 328             //&& stack.top().kind == kind // needed?
 329             && stack.top().from <= from
 330             && stack.top().end >= end) {
 331                 LYXERR(Debug::UNDO, "Undo coalescing: skip entry");
 332                 return;
 333         }
 334
 335         // Undo::ATOMIC are always recorded (no overlapping there).
 336         // As nobody wants all removed character appear one by one when undoing,
 337         // we want combine 'similar' non-ATOMIC undo recordings to one.
 338         if (!undo_finished_
 339             && kind != ATOMIC_UNDO
 340             && !stack.empty()
 341             && !stack.top().bparams
 342             && samePar(stack.top().cell, cell)
 343             && stack.top().kind == kind
 344             && stack.top().from == from
 345             && stack.top().end == end
 346             && stack.top().cur_after == cur_before
 347             && current_time() - stack.top().time <= 2) {
 348                 // reset cur_after; it will be filled correctly by endUndoGroup.
 349                 stack.top().cur_after = CursorData();
 350                 // update the timestamp of the undo element
 351                 stack.top().time = current_time();
 352                 return;
 353         }
 354
 355         LYXERR(Debug::UNDO, "Create undo element of group " << group_id_);
 356         // create the position information of the Undo entry
 357         UndoElement undo(kind,
 358               group_cur_before_.empty() ? cur_before : group_cur_before_,
 359               cell, from, end, nullptr, nullptr, buffer_.isClean(), group_id_);
 360
 361         // fill in the real data to be saved
 362         if (cell.inMathed()) {
 363                 // simply use the whole cell
 364                 MathData & ar = cell.cell();
 365                 undo.array = new MathData(ar.buffer(), ar.begin(), ar.end());
 366         } else {
 367                 // some more effort needed here as 'the whole cell' of the
 368                 // main Text _is_ the whole document.
 369                 // record the relevant paragraphs
 370                 Text const * text = cell.text();
 371                 LBUFERR(text);
 372                 ParagraphList const & plist = text->paragraphs();
 373                 ParagraphList::const_iterator first = plist.begin();
 374                 advance(first, first_pit);
 375                 ParagraphList::const_iterator last = plist.begin();
 376                 advance(last, last_pit + 1);
 377                 undo.pars = new ParagraphList(first, last);
 378         }
 379
 380         // push the undo entry to undo stack
 381         stack.push(undo);
 382         //lyxerr << "undo record: " << stack.top() << endl;
 383 }
 384
 385
 386 void Undo::Private::recordUndo(UndoKind kind,
 387                                DocIterator const & cell,
 388                                pit_type first_pit, pit_type last_pit,
 389                                CursorData const & cur)
 390 {
 391         LASSERT(first_pit <= cell.lastpit(), return);
 392         LASSERT(last_pit <= cell.lastpit(), return);
 393
 394         if (buffer_.isReadonly())
 395                 return;
 396
 397         doRecordUndo(kind, cell, first_pit, last_pit, cur,
 398                 undostack_);
 399
 400         // next time we'll try again to combine entries if possible
 401         undo_finished_ = false;
 402
 403         // If we ran recordUndo, it means that we plan to change the buffer
 404         buffer_.markDirty();
 405
 406         redostack_.clear();
 407 }
 408
 409
 410 void Undo::Private::doRecordUndoBufferParams(CursorData const & cur_before,
 411                                              UndoElementStack & stack)
 412 {
 413         if (!group_level_) {
 414                 LYXERR0("There is no group open (creating one)");
 415                 ++group_id_;
 416         }
 417
 418         LYXERR(Debug::UNDO, "Create full buffer undo element of group " << group_id_);
 419         // create the position information of the Undo entry
 420         UndoElement undo(group_cur_before_.empty() ? cur_before : group_cur_before_,
 421                      buffer_.params(), buffer_.isClean(),
 422                                          group_id_);
 423
 424         // push the undo entry to undo stack
 425         stack.push(undo);
 426 }
 427
 428
 429 void Undo::Private::recordUndoBufferParams(CursorData const & cur)
 430 {
 431         if (buffer_.isReadonly())
 432                 return;
 433
 434         doRecordUndoBufferParams(cur, undostack_);
 435
 436         // next time we'll try again to combine entries if possible
 437         undo_finished_ = false;
 438
 439         // If we ran recordUndo, it means that we plan to change the buffer
 440         buffer_.markDirty();
 441
 442         redostack_.clear();
 443 }
 444
 445
 446 void Undo::Private::doUndoRedoAction(CursorData & cur, UndoElementStack & stack, UndoElementStack & otherstack)
 447 {
 448         // Adjust undo stack and get hold of current undo data.
 449         UndoElement & undo = stack.top();
 450         LYXERR(Debug::UNDO, "Undo element of group " << undo.group_id);
 451         // We'll pop the stack only when we're done with this element. So do NOT
 452         // try to return early.
 453
 454         // We will store in otherstack the part of the document under 'undo'
 455         DocIterator cell_dit = undo.cell.asDocIterator(&buffer_);
 456
 457         if (undo.bparams)
 458                 doRecordUndoBufferParams(undo.cur_after, otherstack);
 459         else {
 460                 LATTEST(undo.end <= cell_dit.lastpit());
 461                 doRecordUndo(ATOMIC_UNDO, cell_dit,
 462                                          undo.from, cell_dit.lastpit() - undo.end, undo.cur_after,
 463                                          otherstack);
 464         }
 465         otherstack.top().cur_after = undo.cur_before;
 466
 467         // This does the actual undo/redo.
 468         //LYXERR0("undo, performing: " << undo);
 469         DocIterator dit = undo.cell.asDocIterator(&buffer_);
 470         if (undo.bparams) {
 471                 // This is a params undo element
 472                 delete otherstack.top().bparams;
 473                 otherstack.top().bparams = new BufferParams(buffer_.params());
 474                 DocumentClassConstPtr olddc = buffer_.params().documentClassPtr();
 475                 buffer_.params() = *undo.bparams;
 476                 cap::switchBetweenClasses(olddc, buffer_.params().documentClassPtr(),
 477                         static_cast<InsetText &>(buffer_.inset()));
 478         } else if (dit.inMathed()) {
 479                 // We stored the full cell here as there is not much to be
 480                 // gained by storing just 'a few' paragraphs (most if not
 481                 // all math inset cells have just one paragraph!)
 482                 //LYXERR0("undo.array: " << *undo.array);
 483                 LBUFERR(undo.array);
 484                 dit.cell().swap(*undo.array);
 485                 dit.inset().setBuffer(buffer_);
 486                 delete undo.array;
 487                 undo.array = nullptr;
 488         } else {
 489                 // Some finer machinery is needed here.
 490                 Text * text = dit.text();
 491                 LBUFERR(text);
 492                 LBUFERR(undo.pars);
 493                 ParagraphList & plist = text->paragraphs();
 494
 495                 // remove new stuff between first and last
 496                 ParagraphList::iterator first = plist.begin();
 497                 advance(first, undo.from);
 498                 ParagraphList::iterator last = plist.begin();
 499                 advance(last, plist.size() - undo.end);
 500                 plist.erase(first, last);
 501
 502                 // re-insert old stuff instead
 503                 first = plist.begin();
 504                 advance(first, undo.from);
 505
 506                 // this ugly stuff is needed until we get rid of the
 507                 // inset_owner backpointer
 508                 ParagraphList::iterator pit = undo.pars->begin();
 509                 ParagraphList::iterator const end = undo.pars->end();
 510                 for (; pit != end; ++pit)
 511                         pit->setInsetOwner(dit.realInset());
 512                 plist.insert(first, undo.pars->begin(), undo.pars->end());
 513
 514                 // set the buffers for insets we created
 515                 ParagraphList::iterator fpit = plist.begin();
 516                 advance(fpit, undo.from);
 517                 ParagraphList::iterator fend = fpit;
 518                 advance(fend, undo.pars->size());
 519                 for (; fpit != fend; ++fpit)
 520                         fpit->setInsetBuffers(buffer_);
 521
 522                 delete undo.pars;
 523                 undo.pars = nullptr;
 524         }
 525
 526         // We'll clean up in release mode.
 527         LASSERT(undo.pars == nullptr, undo.pars = nullptr);
 528         LASSERT(undo.array == nullptr, undo.array = nullptr);
 529
 530         if (!undo.cur_before.empty())
 531                 cur = undo.cur_before;
 532         if (undo.lyx_clean)
 533                 buffer_.markClean();
 534         else
 535                 buffer_.markDirty();
 536         // Now that we're done with undo, we pop it off the stack.
 537         stack.pop();
 538 }
 539
 540
 541 bool Undo::Private::undoRedoAction(CursorData & cur, bool isUndoOperation)
 542 {
 543         if (buffer_.isReadonly())
 544                 return false;
 545
 546         undo_finished_ = true;
 547
 548         UndoElementStack & stack = isUndoOperation ?  undostack_ : redostack_;
 549
 550         if (stack.empty())
 551                 // Nothing to do.
 552                 return false;
 553
 554         UndoElementStack & otherstack = isUndoOperation ? redostack_ : undostack_;
 555
 556         const size_t gid = stack.top().group_id;
 557         while (!stack.empty() && stack.top().group_id == gid)
 558                 doUndoRedoAction(cur, stack, otherstack);
 559         return true;
 560 }
 561
 562
 563 void Undo::finishUndo()
 564 {
 565         // Make sure the next operation will be stored.
 566         d->undo_finished_ = true;
 567 }
 568
 569
 570 bool Undo::undoAction(CursorData & cur)
 571 {
 572         return d->undoRedoAction(cur, true);
 573 }
 574
 575
 576 bool Undo::redoAction(CursorData & cur)
 577 {
 578         return d->undoRedoAction(cur, false);
 579 }
 580
 581
 582 void Undo::beginUndoGroup()
 583 {
 584         if (d->group_level_ == 0) {
 585                 // create a new group
 586                 ++d->group_id_;
 587                 LYXERR(Debug::UNDO, "+++++++ Creating new group " << d->group_id_
 588                        << " for buffer " << &d->buffer_);
 589         }
 590         ++d->group_level_;
 591 }
 592
 593
 594 void Undo::beginUndoGroup(CursorData const & cur_before)
 595 {
 596         beginUndoGroup();
 597         if (d->group_cur_before_.empty())
 598                 d->group_cur_before_ = cur_before;
 599 }
 600
 601
 602 void Undo::endUndoGroup()
 603 {
 604         if (d->group_level_ == 0) {
 605                 LYXERR0("There is no undo group to end here");
 606                 return;
 607         }
 608         --d->group_level_;
 609         if (d->group_level_ == 0) {
 610                 // real end of the group
 611                 d->group_cur_before_ = CursorData();
 612                 LYXERR(Debug::UNDO, "------- End of group " << d->group_id_
 613                        << " of buffer " << &d->buffer_);
 614         }
 615 }
 616
 617
 618 void Undo::endUndoGroup(CursorData const & cur_after)
 619 {
 620         endUndoGroup();
 621         if (!d->undostack_.empty() && d->undostack_.top().cur_after.empty())
 622                 d->undostack_.top().cur_after = cur_after;
 623 }
 624
 625
 626 void Undo::splitUndoGroup(CursorData const & cur)
 627 {
 628         size_t const level = d->group_level_;
 629         d->group_level_ = 1;
 630         endUndoGroup(cur);
 631         beginUndoGroup(cur);
 632         d->group_level_ = level;
 633 }
 634
 635
 636 bool Undo::activeUndoGroup() const
 637 {
 638         return d->group_level_ > 0
 639                 && !d->undostack_.empty()
 640                 && d->undostack_.top().group_id == d->group_id_;
 641 }
 642
 643
 644 void Undo::recordUndo(CursorData const & cur, UndoKind kind)
 645 {
 646         d->recordUndo(kind, cur, cur.pit(), cur.pit(), cur);
 647 }
 648
 649
 650 void Undo::recordUndo(CursorData const & cur, pit_type from, pit_type to)
 651 {
 652         d->recordUndo(ATOMIC_UNDO, cur, from, to, cur);
 653 }
 654
 655
 656 void Undo::recordUndoInset(CursorData const & cur, Inset const * inset)
 657 {
 658         if (!inset || inset == &cur.inset()) {
 659                 DocIterator c = cur;
 660                 c.pop_back();
 661                 d->recordUndo(ATOMIC_UNDO, c, c.pit(), c.pit(), cur);
 662         } else if (inset == cur.nextInset())
 663                 recordUndo(cur);
 664         else
 665                 LYXERR0("Inset not found, no undo stack added.");
 666 }
 667
 668
 669 void Undo::recordUndoBufferParams(CursorData const & cur)
 670 {
 671         d->recordUndoBufferParams(cur);
 672 }
 673
 674
 675 void Undo::recordUndoFullBuffer(CursorData const & cur)
 676 {
 677         // This one may happen outside of the main undo group, so we
 678         // put it in its own subgroup to avoid complaints.
 679         beginUndoGroup();
 680         d->recordUndo(ATOMIC_UNDO, doc_iterator_begin(&d->buffer_),
 681                       0, d->buffer_.paragraphs().size() - 1, cur);
 682         d->recordUndoBufferParams(cur);
 683         endUndoGroup();
 684 }
 685
 686 /// UndoGroupHelper class stuff
 687
 688 class UndoGroupHelper::Impl {
 689         friend class UndoGroupHelper;
 690         set<Buffer *> buffers_;
 691 };
 692
 693
 694 UndoGroupHelper::UndoGroupHelper(Buffer * buf) : d(new UndoGroupHelper::Impl)
 695 {
 696         resetBuffer(buf);
 697 }
 698
 699
 700 UndoGroupHelper::~UndoGroupHelper()
 701 {
 702         for (Buffer * buf : d->buffers_)
 703                 if (theBufferList().isLoaded(buf) || theBufferList().isInternal(buf))
 704                         buf->undo().endUndoGroup();
 705         delete d;
 706 }
 707
 708 void UndoGroupHelper::resetBuffer(Buffer * buf)
 709 {
 710         if (buf && d->buffers_.count(buf) == 0) {
 711                 d->buffers_.insert(buf);
 712                 buf->undo().beginUndoGroup();
 713         }
 714 }
 715
 716
 717 } // namespace lyx