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