ext/scintilla/src/UndoHistory.cxx

   1 // Scintilla source code edit control
   2 /** @file UndoHistory.cxx
   3  ** Manages undo for the document.
   4  **/
   5 // Copyright 1998-2024 by Neil Hodgson <neilh@scintilla.org>
   6 // The License.txt file describes the conditions under which this software may be distributed.
   7
   8 #include <cstddef>
   9 #include <cstdlib>
  10 #include <cstdint>
  11 #include <cassert>
  12 #include <cstring>
  13 #include <cstdio>
  14 #include <cstdarg>
  15 #include <climits>
  16
  17 #include <stdexcept>
  18 #include <string>
  19 #include <string_view>
  20 #include <vector>
  21 #include <optional>
  22 #include <algorithm>
  23 #include <memory>
  24
  25 #include "ScintillaTypes.h"
  26
  27 #include "Debugging.h"
  28
  29 #include "Position.h"
  30 #include "SplitVector.h"
  31 #include "Partitioning.h"
  32 #include "RunStyles.h"
  33 #include "SparseVector.h"
  34 #include "ChangeHistory.h"
  35 #include "CellBuffer.h"
  36 #include "UndoHistory.h"
  37
  38 namespace Scintilla::Internal {
  39
  40 template <typename T>
  41 void VectorTruncate(std::vector<T> &v, size_t length) noexcept {
  42         v.erase(v.begin() + length, v.end());
  43 }
  44
  45 constexpr size_t byteMask = UINT8_MAX;
  46 constexpr size_t byteBits = 8;
  47
  48 size_t ReadValue(const uint8_t *bytes, size_t length) noexcept {
  49         size_t value = 0;
  50         for (size_t i = 0; i < length; i++) {
  51                 value = (value << byteBits) + bytes[i];
  52         }
  53         return value;
  54 }
  55
  56 void WriteValue(uint8_t *bytes, size_t length, size_t value) noexcept {
  57         while (length != 0) {
  58                 --length;
  59                 bytes[length] = value & byteMask;
  60                 value = value >> byteBits;
  61         }
  62 }
  63
  64 size_t ScaledVector::Size() const noexcept {
  65         return bytes.size() / element.size;
  66 }
  67
  68 size_t ScaledVector::ValueAt(size_t index) const noexcept {
  69         return ReadValue(bytes.data() + index * element.size, element.size);
  70 }
  71
  72 intptr_t ScaledVector::SignedValueAt(size_t index) const noexcept {
  73         return ReadValue(bytes.data() + index * element.size, element.size);
  74 }
  75
  76 constexpr SizeMax ElementForValue(size_t value) noexcept {
  77         size_t maxN = byteMask;
  78         size_t i = 1;
  79         while (value > byteMask) {
  80                 i++;
  81                 value >>= byteBits;
  82                 maxN = (maxN << byteBits) + byteMask;
  83         }
  84         return { i, maxN };
  85 }
  86
  87 void ScaledVector::SetValueAt(size_t index, size_t value) {
  88         // Check if value fits, if not then expand
  89         if (value > element.maxValue) {
  90                 const SizeMax elementForValue = ElementForValue(value);
  91                 const size_t length = bytes.size() / element.size;
  92                 std::vector<uint8_t> bytesNew(elementForValue.size * length);
  93                 for (size_t i = 0; i < length; i++) {
  94                         const uint8_t *source = bytes.data() + i * element.size;
  95                         uint8_t *destination = bytesNew.data() + (i+1) * elementForValue.size - element.size;
  96                         memcpy(destination, source, element.size);
  97                 }
  98                 std::swap(bytes, bytesNew);
  99                 element = elementForValue;
 100         }
 101         WriteValue(bytes.data() + index * element.size, element.size, value);
 102 }
 103
 104 void ScaledVector::ClearValueAt(size_t index) noexcept {
 105         // 0 fits in any size element so no expansion needed so no exceptions
 106         WriteValue(bytes.data() + index * element.size, element.size, 0);
 107 }
 108
 109 void ScaledVector::Clear() noexcept {
 110         bytes.clear();
 111 }
 112
 113 void ScaledVector::Truncate(size_t length) noexcept {
 114         VectorTruncate(bytes, length * element.size);
 115         assert(bytes.size() == length * element.size);
 116 }
 117
 118 void ScaledVector::ReSize(size_t length) {
 119         bytes.resize(length * element.size);
 120 }
 121
 122 void ScaledVector::PushBack() {
 123         bytes.resize(bytes.size() + element.size);
 124 }
 125
 126 size_t ScaledVector::SizeInBytes() const noexcept {
 127         return bytes.size();
 128 }
 129
 130 UndoActionType::UndoActionType() noexcept : at(ActionType::insert), mayCoalesce(false) {
 131 }
 132
 133 UndoActions::UndoActions() noexcept = default;
 134
 135 void UndoActions::Truncate(size_t length) noexcept {
 136         VectorTruncate(types, length);
 137         assert(types.size() == length);
 138         positions.Truncate(length);
 139         lengths.Truncate(length);
 140 }
 141
 142 void UndoActions::PushBack() {
 143         types.emplace_back();
 144         positions.PushBack();
 145         lengths.PushBack();
 146 }
 147
 148 void UndoActions::Clear() noexcept {
 149         types.clear();
 150         positions.Clear();
 151         lengths.Clear();
 152 }
 153
 154 intptr_t UndoActions::SSize() const noexcept {
 155         return types.size();
 156 }
 157
 158 void UndoActions::Create(size_t index, ActionType at_, Sci::Position position_, Sci::Position lenData_, bool mayCoalesce_) {
 159         types[index].at = at_;
 160         types[index].mayCoalesce = mayCoalesce_;
 161         positions.SetValueAt(index, position_);
 162         lengths.SetValueAt(index, lenData_);
 163 }
 164
 165 bool UndoActions::AtStart(size_t index) const noexcept {
 166         if (index == 0) {
 167                 return true;
 168         }
 169         return !types[index-1].mayCoalesce;
 170 }
 171
 172 size_t UndoActions::LengthTo(size_t index) const noexcept {
 173         size_t sum = 0;
 174         for (size_t act = 0; act < index; act++) {
 175                 sum += lengths.ValueAt(act);
 176         }
 177         return sum;
 178 }
 179
 180 Sci::Position UndoActions::Position(int action) const noexcept {
 181         return positions.SignedValueAt(action);
 182 }
 183 Sci::Position UndoActions::Length(int action) const noexcept {
 184         return lengths.SignedValueAt(action);
 185 }
 186
 187 void ScrapStack::Clear() noexcept {
 188         stack.clear();
 189         current = 0;
 190 }
 191
 192 const char *ScrapStack::Push(const char *text, size_t length) {
 193         if (current < stack.length()) {
 194                 stack.resize(current);
 195         }
 196         stack.append(text, length);
 197         current = stack.length();
 198         return stack.data() + current - length;
 199 }
 200
 201 void ScrapStack::SetCurrent(size_t position) noexcept {
 202         current = position;
 203 }
 204
 205 void ScrapStack::MoveForward(size_t length) noexcept {
 206         if ((current + length) <= stack.length()) {
 207                 current += length;
 208         }
 209 }
 210
 211 void ScrapStack::MoveBack(size_t length) noexcept {
 212         if (current >= length) {
 213                 current -= length;
 214         }
 215 }
 216
 217 const char *ScrapStack::CurrentText() const noexcept {
 218         return stack.data() + current;
 219 }
 220
 221 const char *ScrapStack::TextAt(size_t position) const noexcept {
 222         return stack.data() + position;
 223 }
 224
 225 // The undo history stores a sequence of user operations that represent the user's view of the
 226 // commands executed on the text.
 227 // Each user operation contains a sequence of text insertion and text deletion actions.
 228 // All the user operations are stored in a list of individual actions.
 229 // A false 'mayCoalesce' flag acts as an end to a user operation.
 230 // Initially there are no actions in the history.
 231 // As each action is performed, it is recorded in the history. The action may either become
 232 // part of the current user operation or may start a new user operation. If it is to be part of the
 233 // current operation, then 'mayCoalesce' is true. If it is to be part of a new operation, the
 234 // 'mayCoalesce' flag of the previous action is set false.
 235 // The decision of whether to start a new user operation is based upon two factors. If a
 236 // compound operation has been explicitly started by calling BeginUndoAction and no matching
 237 // EndUndoAction (these calls nest) has been called, then the action is coalesced into the current
 238 // operation. If there is no outstanding BeginUndoAction call then a new operation is started
 239 // unless it looks as if the new action is caused by the user typing or deleting a stream of text.
 240 // Sequences that look like typing or deletion are coalesced into a single user operation.
 241
 242 int UndoHistory::PreviousAction() const noexcept {
 243         return currentAction - 1;
 244 }
 245
 246 UndoHistory::UndoHistory() {
 247         scraps = std::make_unique<ScrapStack>();
 248 }
 249
 250 UndoHistory::~UndoHistory() noexcept = default;
 251
 252 const char *UndoHistory::AppendAction(ActionType at, Sci::Position position, const char *data, Sci::Position lengthData,
 253         bool &startSequence, bool mayCoalesce) {
 254         //Platform::DebugPrintf("%% %d action %d %d %d\n", at, position, lengthData, currentAction);
 255         //Platform::DebugPrintf("^ %d action %d %d\n", actions[currentAction - 1].at,
 256         //      actions[currentAction - 1].position, actions[currentAction - 1].lenData);
 257         if (currentAction < savePoint) {
 258                 savePoint = -1;
 259                 if (!detach) {
 260                         detach = currentAction;
 261                 }
 262         } else if (detach && (*detach > currentAction)) {
 263                 detach = currentAction;
 264         }
 265         if (undoSequenceDepth > 0) {
 266                 // Actions not at top level are always coalesced unless this is after return to top level
 267                 mayCoalesce = true;
 268         }
 269         bool coalesce = true;
 270         if (currentAction >= 1) {
 271                 int targetAct = currentAction - 1;
 272                 if (0 == undoSequenceDepth) {
 273                         // Top level actions may not always be coalesced
 274                         // Container actions may forward the coalesce state of Scintilla Actions.
 275                         while ((targetAct > 0) && (actions.types[targetAct].at == ActionType::container) && actions.types[targetAct].mayCoalesce) {
 276                                 targetAct--;
 277                         }
 278                         // See if current action can be coalesced into previous action
 279                         // Will work if both are inserts or deletes and position is same
 280                         if ((currentAction == savePoint) || (currentAction == tentativePoint)) {
 281                                 coalesce = false;
 282                         } else if (!mayCoalesce || !actions.types[targetAct].mayCoalesce) {
 283                                 coalesce = false;
 284                         } else if (at == ActionType::container || actions.types[targetAct].at == ActionType::container) {
 285                                 ;       // A coalescible containerAction
 286                         } else if ((at != actions.types[targetAct].at)) { // } && (!actions.AtStart(targetAct))) {
 287                                 coalesce = false;
 288                         } else if ((at == ActionType::insert) &&
 289                                    (position != (actions.Position(targetAct) + actions.Length(targetAct)))) {
 290                                 // Insertions must be immediately after to coalesce
 291                                 coalesce = false;
 292                         } else if (at == ActionType::remove) {
 293                                 if ((lengthData == 1) || (lengthData == 2)) {
 294                                         if ((position + lengthData) == actions.Position(targetAct)) {
 295                                                 ; // Backspace -> OK
 296                                         } else if (position == actions.Position(targetAct)) {
 297                                                 ; // Delete -> OK
 298                                         } else {
 299                                                 // Removals must be at same position to coalesce
 300                                                 coalesce = false;
 301                                         }
 302                                 } else {
 303                                         // Removals must be of one character to coalesce
 304                                         coalesce = false;
 305                                 }
 306                         } else {
 307                                 // Action coalesced.
 308                         }
 309
 310                 } else {
 311                         // Actions not at top level are always coalesced unless this is after return to top level
 312                         if (!actions.types[targetAct].mayCoalesce)
 313                                 coalesce = false;
 314                 }
 315         } else {
 316                 coalesce = false;
 317         }
 318         startSequence = !coalesce;
 319         // Maybe close previous action
 320         if ((currentAction > 0) && startSequence) {
 321                 actions.types[PreviousAction()].mayCoalesce = false;
 322         }
 323         const char *dataNew = lengthData ? scraps->Push(data, lengthData) : nullptr;
 324         if (currentAction >= actions.SSize()) {
 325                 actions.PushBack();
 326         } else {
 327                 actions.Truncate(currentAction+1);
 328         }
 329         actions.Create(currentAction, at, position, lengthData, mayCoalesce);
 330         currentAction++;
 331         return dataNew;
 332 }
 333
 334 void UndoHistory::BeginUndoAction(bool mayCoalesce) noexcept {
 335         if (undoSequenceDepth == 0) {
 336                 if (currentAction > 0) {
 337                         actions.types[PreviousAction()].mayCoalesce = mayCoalesce;
 338                 }
 339         }
 340         undoSequenceDepth++;
 341 }
 342
 343 void UndoHistory::EndUndoAction() noexcept {
 344         PLATFORM_ASSERT(undoSequenceDepth > 0);
 345         undoSequenceDepth--;
 346         if (0 == undoSequenceDepth) {
 347                 if (currentAction > 0) {
 348                         actions.types[PreviousAction()].mayCoalesce = false;
 349                 }
 350         }
 351 }
 352
 353 int UndoHistory::UndoSequenceDepth() const noexcept {
 354         return undoSequenceDepth;
 355 }
 356
 357 void UndoHistory::DropUndoSequence() noexcept {
 358         undoSequenceDepth = 0;
 359 }
 360
 361 void UndoHistory::DeleteUndoHistory() noexcept {
 362         actions.Clear();
 363         currentAction = 0;
 364         savePoint = 0;
 365         tentativePoint = -1;
 366         scraps->Clear();
 367         memory = {};
 368 }
 369
 370 int UndoHistory::Actions() const noexcept {
 371         return static_cast<int>(actions.SSize());
 372 }
 373
 374 void UndoHistory::SetSavePoint(int action) noexcept {
 375         savePoint = action;
 376 }
 377
 378 int UndoHistory::SavePoint() const noexcept {
 379         return savePoint;
 380 }
 381
 382 void UndoHistory::SetSavePoint() noexcept {
 383         savePoint = currentAction;
 384         detach.reset();
 385 }
 386
 387 bool UndoHistory::IsSavePoint() const noexcept {
 388         return savePoint == currentAction;
 389 }
 390
 391 bool UndoHistory::BeforeSavePoint() const noexcept {
 392         return (savePoint < 0) || (savePoint > currentAction);
 393 }
 394
 395 bool UndoHistory::PreviousBeforeSavePoint() const noexcept {
 396         return (savePoint < 0) || (savePoint >= currentAction);
 397 }
 398
 399 bool UndoHistory::BeforeReachableSavePoint() const noexcept {
 400         return (savePoint > 0) && (savePoint > currentAction);
 401 }
 402
 403 bool UndoHistory::AfterSavePoint() const noexcept {
 404         return (savePoint >= 0) && (savePoint <= currentAction);
 405 }
 406
 407 void UndoHistory::SetDetachPoint(int action) noexcept {
 408         if (action == -1) {
 409                 detach = {};
 410         } else {
 411                 detach = action;
 412         }
 413 }
 414
 415 int UndoHistory::DetachPoint() const noexcept {
 416         return detach.value_or(-1);
 417 }
 418
 419 bool UndoHistory::AfterDetachPoint() const noexcept {
 420         return detach && (*detach < currentAction);
 421 }
 422
 423 bool UndoHistory::AfterOrAtDetachPoint() const noexcept {
 424         return detach && (*detach <= currentAction);
 425 }
 426
 427 intptr_t UndoHistory::Delta(int action) const noexcept {
 428         intptr_t sizeChange = 0;
 429         for (int act = 0; act < action; act++) {
 430                 const intptr_t lengthChange = actions.Length(act);
 431                 sizeChange += (actions.types[act].at == ActionType::insert) ? lengthChange : -lengthChange;
 432         }
 433         return sizeChange;
 434 }
 435
 436 bool UndoHistory::Validate(intptr_t lengthDocument) const noexcept {
 437         // Check history for validity
 438         const intptr_t sizeChange = Delta(currentAction);
 439         if (sizeChange > lengthDocument) {
 440                 // Current document size too small for changes made in undo history.
 441                 return false;
 442         }
 443         const intptr_t lengthOriginal = lengthDocument - sizeChange;
 444         intptr_t lengthCurrent = lengthOriginal;
 445         for (int act = 0; act < actions.SSize(); act++) {
 446                 const intptr_t lengthChange = actions.Length(act);
 447                 if (actions.Position(act) > lengthCurrent) {
 448                         // Change outside document.
 449                         return false;
 450                 }
 451                 lengthCurrent += (actions.types[act].at == ActionType::insert) ? lengthChange : -lengthChange;
 452                 if (lengthCurrent < 0) {
 453                         return false;
 454                 }
 455         }
 456         return true;
 457 }
 458
 459 void UndoHistory::SetCurrent(int action, intptr_t lengthDocument) {
 460         // Find position in scraps for action
 461         memory = {};
 462         const size_t lengthSum = actions.LengthTo(action);
 463         scraps->SetCurrent(lengthSum);
 464         currentAction = action;
 465         if (!Validate(lengthDocument)) {
 466                 currentAction = 0;
 467                 DeleteUndoHistory();
 468                 throw std::runtime_error("UndoHistory::SetCurrent: invalid undo history.");
 469         }
 470 }
 471
 472 int UndoHistory::Current() const noexcept {
 473         return currentAction;
 474 }
 475
 476 int UndoHistory::Type(int action) const noexcept {
 477         const int baseType = static_cast<int>(actions.types[action].at);
 478         const int open = actions.types[action].mayCoalesce ? coalesceFlag : 0;
 479         return baseType | open;
 480 }
 481
 482 Sci::Position UndoHistory::Position(int action) const noexcept {
 483         return actions.Position(action);
 484 }
 485
 486 Sci::Position UndoHistory::Length(int action) const noexcept {
 487         return actions.Length(action);
 488 }
 489
 490 std::string_view UndoHistory::Text(int action) noexcept {
 491         // Assumes first call after any changes is for action 0.
 492         // TODO: may need to invalidate memory in other circumstances
 493         if (action == 0) {
 494                 memory = {};
 495         }
 496         int act = 0;
 497         size_t position = 0;
 498         if (memory && memory->act <= action) {
 499                 act = memory->act;
 500                 position = memory->position;
 501         }
 502         for (; act < action; act++) {
 503                 position += actions.Length(act);
 504         }
 505         const size_t length = actions.Length(action);
 506         const char *scrap = scraps->TextAt(position);
 507         memory = {action, position};
 508         return {scrap, length};
 509 }
 510
 511 void UndoHistory::PushUndoActionType(int type, Sci::Position position) {
 512         actions.PushBack();
 513         actions.Create(actions.SSize()-1, static_cast<ActionType>(type & byteMask),
 514                 position, 0, type & coalesceFlag);
 515 }
 516
 517 void UndoHistory::ChangeLastUndoActionText(size_t length, const char *text) {
 518         assert(actions.lengths.ValueAt(actions.SSize()-1) == 0);
 519         actions.lengths.SetValueAt(actions.SSize()-1, length);
 520         scraps->Push(text, length);
 521 }
 522
 523 void UndoHistory::SetTentative(int action) noexcept {
 524         tentativePoint = action;
 525 }
 526
 527 int UndoHistory::TentativePoint() const noexcept {
 528         return tentativePoint;
 529 }
 530
 531 void UndoHistory::TentativeStart() noexcept {
 532         tentativePoint = currentAction;
 533 }
 534
 535 void UndoHistory::TentativeCommit() noexcept {
 536         tentativePoint = -1;
 537         // Truncate undo history
 538         actions.Truncate(currentAction);
 539 }
 540
 541 bool UndoHistory::TentativeActive() const noexcept {
 542         return tentativePoint >= 0;
 543 }
 544
 545 int UndoHistory::TentativeSteps() const noexcept {
 546         // Drop any trailing startAction
 547         if (tentativePoint >= 0)
 548                 return currentAction - tentativePoint;
 549         return -1;
 550 }
 551
 552 bool UndoHistory::CanUndo() const noexcept {
 553         return (currentAction > 0) && (actions.SSize() != 0);
 554 }
 555
 556 int UndoHistory::StartUndo() const noexcept {
 557         assert(currentAction >= 0);
 558
 559         // Count the steps in this action
 560         if (currentAction == 0) {
 561                 return 0;
 562         }
 563
 564         int act = currentAction - 1;
 565
 566         while (act > 0 && !actions.AtStart(act)) {
 567                 act--;
 568         }
 569         return currentAction - act;
 570 }
 571
 572 Action UndoHistory::GetUndoStep() const noexcept {
 573         const int previousAction = PreviousAction();
 574         Action acta {
 575                 actions.types[previousAction].at,
 576                 actions.types[previousAction].mayCoalesce,
 577                 actions.Position(previousAction),
 578                 nullptr,
 579                 actions.Length(previousAction)
 580         };
 581         if (acta.lenData) {
 582                 acta.data = scraps->CurrentText() - acta.lenData;
 583         }
 584         return acta;
 585 }
 586
 587 void UndoHistory::CompletedUndoStep() noexcept {
 588         scraps->MoveBack(actions.Length(PreviousAction()));
 589         currentAction--;
 590 }
 591
 592 bool UndoHistory::CanRedo() const noexcept {
 593         return actions.SSize() > currentAction;
 594 }
 595
 596 int UndoHistory::StartRedo() const noexcept {
 597         // Count the steps in this action
 598
 599         if (currentAction >= actions.SSize()) {
 600                 // Already at end so can't redo
 601                 return 0;
 602         }
 603
 604         // Slightly unusual logic handles case where last action still has mayCoalesce.
 605         // Could set mayCoalesce of last action to false in StartUndo but this state is
 606         // visible to applications so should not be changed.
 607         const int maxAction = Actions() - 1;
 608         int act = currentAction;
 609         while (act <= maxAction && actions.types[act].mayCoalesce) {
 610                 act++;
 611         }
 612         act = std::min(act, maxAction);
 613         return act - currentAction + 1;
 614 }
 615
 616 Action UndoHistory::GetRedoStep() const noexcept {
 617         Action acta{
 618                 actions.types[currentAction].at,
 619                 actions.types[currentAction].mayCoalesce,
 620                 actions.Position(currentAction),
 621                 nullptr,
 622                 actions.Length(currentAction)
 623         };
 624         if (acta.lenData) {
 625                 acta.data = scraps->CurrentText();
 626         }
 627         return acta;
 628 }
 629
 630 void UndoHistory::CompletedRedoStep() noexcept {
 631         scraps->MoveForward(actions.Length(currentAction));
 632         currentAction++;
 633 }
 634
 635 }