1 // Scintilla source code edit control
2 /** @file CellBuffer.cxx
3 ** Manages a buffer of cells.
5 // Copyright 1998-2001 by Neil Hodgson <neilh@scintilla.org>
6 // The License.txt file describes the conditions under which this software may be distributed.
21 #include "Scintilla.h"
23 #include "SplitVector.h"
24 #include "Partitioning.h"
25 #include "CellBuffer.h"
26 #include "UniConversion.h"
28 using namespace Scintilla
;
30 LineVector::LineVector() : starts(256), perLine(0) {
34 LineVector::~LineVector() {
38 void LineVector::Init() {
45 void LineVector::SetPerLine(PerLine
*pl
) {
49 void LineVector::InsertText(Sci::Line line
, Sci::Position delta
) {
50 starts
.InsertText(line
, delta
);
53 void LineVector::InsertLine(Sci::Line line
, Sci::Position position
, bool lineStart
) {
54 starts
.InsertPartition(line
, position
);
56 if ((line
> 0) && lineStart
)
58 perLine
->InsertLine(line
);
62 void LineVector::SetLineStart(Sci::Line line
, Sci::Position position
) {
63 starts
.SetPartitionStartPosition(line
, position
);
66 void LineVector::RemoveLine(Sci::Line line
) {
67 starts
.RemovePartition(line
);
69 perLine
->RemoveLine(line
);
73 Sci::Line
LineVector::LineFromPosition(Sci::Position pos
) const {
74 return starts
.PartitionFromPosition(pos
);
84 Action::Action(Action
&&other
) {
86 position
= other
.position
;
87 data
= std::move(other
.data
);
88 lenData
= other
.lenData
;
89 mayCoalesce
= other
.mayCoalesce
;
95 void Action::Create(actionType at_
, Sci::Position position_
, const char *data_
, Sci::Position lenData_
, bool mayCoalesce_
) {
100 data
= std::make_unique
<char[]>(lenData_
);
101 memcpy(&data
[0], data_
, lenData_
);
104 mayCoalesce
= mayCoalesce_
;
107 void Action::Clear() {
112 // The undo history stores a sequence of user operations that represent the user's view of the
113 // commands executed on the text.
114 // Each user operation contains a sequence of text insertion and text deletion actions.
115 // All the user operations are stored in a list of individual actions with 'start' actions used
116 // as delimiters between user operations.
117 // Initially there is one start action in the history.
118 // As each action is performed, it is recorded in the history. The action may either become
119 // part of the current user operation or may start a new user operation. If it is to be part of the
120 // current operation, then it overwrites the current last action. If it is to be part of a new
121 // operation, it is appended after the current last action.
122 // After writing the new action, a new start action is appended at the end of the history.
123 // The decision of whether to start a new user operation is based upon two factors. If a
124 // compound operation has been explicitly started by calling BeginUndoAction and no matching
125 // EndUndoAction (these calls nest) has been called, then the action is coalesced into the current
126 // operation. If there is no outstanding BeginUndoAction call then a new operation is started
127 // unless it looks as if the new action is caused by the user typing or deleting a stream of text.
128 // Sequences that look like typing or deletion are coalesced into a single user operation.
130 UndoHistory::UndoHistory() {
135 undoSequenceDepth
= 0;
139 actions
[currentAction
].Create(startAction
);
142 UndoHistory::~UndoHistory() {
145 void UndoHistory::EnsureUndoRoom() {
146 // Have to test that there is room for 2 more actions in the array
147 // as two actions may be created by the calling function
148 if (static_cast<size_t>(currentAction
) >= (actions
.size() - 2)) {
149 // Run out of undo nodes so extend the array
150 actions
.resize(actions
.size() * 2);
154 const char *UndoHistory::AppendAction(actionType at
, Sci::Position position
, const char *data
, Sci::Position lengthData
,
155 bool &startSequence
, bool mayCoalesce
) {
157 //Platform::DebugPrintf("%% %d action %d %d %d\n", at, position, lengthData, currentAction);
158 //Platform::DebugPrintf("^ %d action %d %d\n", actions[currentAction - 1].at,
159 // actions[currentAction - 1].position, actions[currentAction - 1].lenData);
160 if (currentAction
< savePoint
) {
163 int oldCurrentAction
= currentAction
;
164 if (currentAction
>= 1) {
165 if (0 == undoSequenceDepth
) {
166 // Top level actions may not always be coalesced
168 const Action
*actPrevious
= &(actions
[currentAction
+ targetAct
]);
169 // Container actions may forward the coalesce state of Scintilla Actions.
170 while ((actPrevious
->at
== containerAction
) && actPrevious
->mayCoalesce
) {
172 actPrevious
= &(actions
[currentAction
+ targetAct
]);
174 // See if current action can be coalesced into previous action
175 // Will work if both are inserts or deletes and position is same
176 if ((currentAction
== savePoint
) || (currentAction
== tentativePoint
)) {
178 } else if (!actions
[currentAction
].mayCoalesce
) {
179 // Not allowed to coalesce if this set
181 } else if (!mayCoalesce
|| !actPrevious
->mayCoalesce
) {
183 } else if (at
== containerAction
|| actions
[currentAction
].at
== containerAction
) {
184 ; // A coalescible containerAction
185 } else if ((at
!= actPrevious
->at
) && (actPrevious
->at
!= startAction
)) {
187 } else if ((at
== insertAction
) &&
188 (position
!= (actPrevious
->position
+ actPrevious
->lenData
))) {
189 // Insertions must be immediately after to coalesce
191 } else if (at
== removeAction
) {
192 if ((lengthData
== 1) || (lengthData
== 2)) {
193 if ((position
+ lengthData
) == actPrevious
->position
) {
195 } else if (position
== actPrevious
->position
) {
198 // Removals must be at same position to coalesce
202 // Removals must be of one character to coalesce
210 // Actions not at top level are always coalesced unless this is after return to top level
211 if (!actions
[currentAction
].mayCoalesce
)
217 startSequence
= oldCurrentAction
!= currentAction
;
218 const int actionWithData
= currentAction
;
219 actions
[currentAction
].Create(at
, position
, data
, lengthData
, mayCoalesce
);
221 actions
[currentAction
].Create(startAction
);
222 maxAction
= currentAction
;
223 return actions
[actionWithData
].data
.get();
226 void UndoHistory::BeginUndoAction() {
228 if (undoSequenceDepth
== 0) {
229 if (actions
[currentAction
].at
!= startAction
) {
231 actions
[currentAction
].Create(startAction
);
232 maxAction
= currentAction
;
234 actions
[currentAction
].mayCoalesce
= false;
239 void UndoHistory::EndUndoAction() {
240 PLATFORM_ASSERT(undoSequenceDepth
> 0);
243 if (0 == undoSequenceDepth
) {
244 if (actions
[currentAction
].at
!= startAction
) {
246 actions
[currentAction
].Create(startAction
);
247 maxAction
= currentAction
;
249 actions
[currentAction
].mayCoalesce
= false;
253 void UndoHistory::DropUndoSequence() {
254 undoSequenceDepth
= 0;
257 void UndoHistory::DeleteUndoHistory() {
258 for (int i
= 1; i
< maxAction
; i
++)
262 actions
[currentAction
].Create(startAction
);
267 void UndoHistory::SetSavePoint() {
268 savePoint
= currentAction
;
271 bool UndoHistory::IsSavePoint() const {
272 return savePoint
== currentAction
;
275 void UndoHistory::TentativeStart() {
276 tentativePoint
= currentAction
;
279 void UndoHistory::TentativeCommit() {
281 // Truncate undo history
282 maxAction
= currentAction
;
285 int UndoHistory::TentativeSteps() {
286 // Drop any trailing startAction
287 if (actions
[currentAction
].at
== startAction
&& currentAction
> 0)
289 if (tentativePoint
>= 0)
290 return currentAction
- tentativePoint
;
295 bool UndoHistory::CanUndo() const {
296 return (currentAction
> 0) && (maxAction
> 0);
299 int UndoHistory::StartUndo() {
300 // Drop any trailing startAction
301 if (actions
[currentAction
].at
== startAction
&& currentAction
> 0)
304 // Count the steps in this action
305 int act
= currentAction
;
306 while (actions
[act
].at
!= startAction
&& act
> 0) {
309 return currentAction
- act
;
312 const Action
&UndoHistory::GetUndoStep() const {
313 return actions
[currentAction
];
316 void UndoHistory::CompletedUndoStep() {
320 bool UndoHistory::CanRedo() const {
321 return maxAction
> currentAction
;
324 int UndoHistory::StartRedo() {
325 // Drop any leading startAction
326 if (currentAction
< maxAction
&& actions
[currentAction
].at
== startAction
)
329 // Count the steps in this action
330 int act
= currentAction
;
331 while (act
< maxAction
&& actions
[act
].at
!= startAction
) {
334 return act
- currentAction
;
337 const Action
&UndoHistory::GetRedoStep() const {
338 return actions
[currentAction
];
341 void UndoHistory::CompletedRedoStep() {
345 CellBuffer::CellBuffer(bool hasStyles_
) :
346 hasStyles(hasStyles_
) {
349 collectingUndo
= true;
352 CellBuffer::~CellBuffer() {
355 char CellBuffer::CharAt(Sci::Position position
) const {
356 return substance
.ValueAt(position
);
359 void CellBuffer::GetCharRange(char *buffer
, Sci::Position position
, Sci::Position lengthRetrieve
) const {
360 if (lengthRetrieve
<= 0)
364 if ((position
+ lengthRetrieve
) > substance
.Length()) {
365 Platform::DebugPrintf("Bad GetCharRange %d for %d of %d\n", position
,
366 lengthRetrieve
, substance
.Length());
369 substance
.GetRange(buffer
, position
, lengthRetrieve
);
372 char CellBuffer::StyleAt(Sci::Position position
) const {
373 return hasStyles
? style
.ValueAt(position
) : 0;
376 void CellBuffer::GetStyleRange(unsigned char *buffer
, Sci::Position position
, Sci::Position lengthRetrieve
) const {
377 if (lengthRetrieve
< 0)
382 std::fill(buffer
, buffer
+ lengthRetrieve
, static_cast<unsigned char>(0));
385 if ((position
+ lengthRetrieve
) > style
.Length()) {
386 Platform::DebugPrintf("Bad GetStyleRange %d for %d of %d\n", position
,
387 lengthRetrieve
, style
.Length());
390 style
.GetRange(reinterpret_cast<char *>(buffer
), position
, lengthRetrieve
);
393 const char *CellBuffer::BufferPointer() {
394 return substance
.BufferPointer();
397 const char *CellBuffer::RangePointer(Sci::Position position
, Sci::Position rangeLength
) {
398 return substance
.RangePointer(position
, rangeLength
);
401 Sci::Position
CellBuffer::GapPosition() const {
402 return static_cast<Sci::Position
>(substance
.GapPosition());
405 // The char* returned is to an allocation owned by the undo history
406 const char *CellBuffer::InsertString(Sci::Position position
, const char *s
, Sci::Position insertLength
, bool &startSequence
) {
407 // InsertString and DeleteChars are the bottleneck though which all changes occur
408 const char *data
= s
;
410 if (collectingUndo
) {
411 // Save into the undo/redo stack, but only the characters - not the formatting
412 // This takes up about half load time
413 data
= uh
.AppendAction(insertAction
, position
, s
, insertLength
, startSequence
);
416 BasicInsertString(position
, s
, insertLength
);
421 bool CellBuffer::SetStyleAt(Sci::Position position
, char styleValue
) {
425 const char curVal
= style
.ValueAt(position
);
426 if (curVal
!= styleValue
) {
427 style
.SetValueAt(position
, styleValue
);
434 bool CellBuffer::SetStyleFor(Sci::Position position
, Sci::Position lengthStyle
, char styleValue
) {
438 bool changed
= false;
439 PLATFORM_ASSERT(lengthStyle
== 0 ||
440 (lengthStyle
> 0 && lengthStyle
+ position
<= style
.Length()));
441 while (lengthStyle
--) {
442 const char curVal
= style
.ValueAt(position
);
443 if (curVal
!= styleValue
) {
444 style
.SetValueAt(position
, styleValue
);
452 // The char* returned is to an allocation owned by the undo history
453 const char *CellBuffer::DeleteChars(Sci::Position position
, Sci::Position deleteLength
, bool &startSequence
) {
454 // InsertString and DeleteChars are the bottleneck though which all changes occur
455 PLATFORM_ASSERT(deleteLength
> 0);
456 const char *data
= 0;
458 if (collectingUndo
) {
459 // Save into the undo/redo stack, but only the characters - not the formatting
460 // The gap would be moved to position anyway for the deletion so this doesn't cost extra
461 data
= substance
.RangePointer(position
, deleteLength
);
462 data
= uh
.AppendAction(removeAction
, position
, data
, deleteLength
, startSequence
);
465 BasicDeleteChars(position
, deleteLength
);
470 Sci::Position
CellBuffer::Length() const {
471 return static_cast<Sci::Position
>(substance
.Length());
474 void CellBuffer::Allocate(Sci::Position newSize
) {
475 substance
.ReAllocate(newSize
);
477 style
.ReAllocate(newSize
);
481 void CellBuffer::SetLineEndTypes(int utf8LineEnds_
) {
482 if (utf8LineEnds
!= utf8LineEnds_
) {
483 utf8LineEnds
= utf8LineEnds_
;
488 bool CellBuffer::ContainsLineEnd(const char *s
, Sci::Position length
) const {
489 unsigned char chBeforePrev
= 0;
490 unsigned char chPrev
= 0;
491 for (Sci::Position i
= 0; i
< length
; i
++) {
492 const unsigned char ch
= s
[i
];
493 if ((ch
== '\r') || (ch
== '\n')) {
495 } else if (utf8LineEnds
) {
496 const unsigned char back3
[3] = { chBeforePrev
, chPrev
, ch
};
497 if (UTF8IsSeparator(back3
) || UTF8IsNEL(back3
+ 1)) {
501 chBeforePrev
= chPrev
;
507 void CellBuffer::SetPerLine(PerLine
*pl
) {
511 Sci::Line
CellBuffer::Lines() const {
515 Sci::Position
CellBuffer::LineStart(Sci::Line line
) const {
518 else if (line
>= Lines())
521 return lv
.LineStart(line
);
524 bool CellBuffer::IsReadOnly() const {
528 void CellBuffer::SetReadOnly(bool set
) {
532 void CellBuffer::SetSavePoint() {
536 bool CellBuffer::IsSavePoint() const {
537 return uh
.IsSavePoint();
540 void CellBuffer::TentativeStart() {
544 void CellBuffer::TentativeCommit() {
545 uh
.TentativeCommit();
548 int CellBuffer::TentativeSteps() {
549 return uh
.TentativeSteps();
552 bool CellBuffer::TentativeActive() const {
553 return uh
.TentativeActive();
558 void CellBuffer::InsertLine(Sci::Line line
, Sci::Position position
, bool lineStart
) {
559 lv
.InsertLine(line
, position
, lineStart
);
562 void CellBuffer::RemoveLine(Sci::Line line
) {
566 bool CellBuffer::UTF8LineEndOverlaps(Sci::Position position
) const {
567 const unsigned char bytes
[] = {
568 static_cast<unsigned char>(substance
.ValueAt(position
-2)),
569 static_cast<unsigned char>(substance
.ValueAt(position
-1)),
570 static_cast<unsigned char>(substance
.ValueAt(position
)),
571 static_cast<unsigned char>(substance
.ValueAt(position
+1)),
573 return UTF8IsSeparator(bytes
) || UTF8IsSeparator(bytes
+1) || UTF8IsNEL(bytes
+1);
576 void CellBuffer::ResetLineEnds() {
577 // Reinitialize line data -- too much work to preserve
580 const Sci::Position position
= 0;
581 const Sci::Position length
= Length();
582 Sci::Line lineInsert
= 1;
583 const bool atLineStart
= true;
584 lv
.InsertText(lineInsert
-1, length
);
585 unsigned char chBeforePrev
= 0;
586 unsigned char chPrev
= 0;
587 for (Sci::Position i
= 0; i
< length
; i
++) {
588 const unsigned char ch
= substance
.ValueAt(position
+ i
);
590 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
592 } else if (ch
== '\n') {
593 if (chPrev
== '\r') {
594 // Patch up what was end of line
595 lv
.SetLineStart(lineInsert
- 1, (position
+ i
) + 1);
597 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
600 } else if (utf8LineEnds
) {
601 const unsigned char back3
[3] = {chBeforePrev
, chPrev
, ch
};
602 if (UTF8IsSeparator(back3
) || UTF8IsNEL(back3
+1)) {
603 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
607 chBeforePrev
= chPrev
;
612 void CellBuffer::BasicInsertString(Sci::Position position
, const char *s
, Sci::Position insertLength
) {
613 if (insertLength
== 0)
615 PLATFORM_ASSERT(insertLength
> 0);
617 const unsigned char chAfter
= substance
.ValueAt(position
);
618 bool breakingUTF8LineEnd
= false;
619 if (utf8LineEnds
&& UTF8IsTrailByte(chAfter
)) {
620 breakingUTF8LineEnd
= UTF8LineEndOverlaps(position
);
623 substance
.InsertFromArray(position
, s
, 0, insertLength
);
625 style
.InsertValue(position
, insertLength
, 0);
628 Sci::Line lineInsert
= lv
.LineFromPosition(position
) + 1;
629 const bool atLineStart
= lv
.LineStart(lineInsert
-1) == position
;
630 // Point all the lines after the insertion point further along in the buffer
631 lv
.InsertText(lineInsert
-1, insertLength
);
632 unsigned char chBeforePrev
= substance
.ValueAt(position
- 2);
633 unsigned char chPrev
= substance
.ValueAt(position
- 1);
634 if (chPrev
== '\r' && chAfter
== '\n') {
635 // Splitting up a crlf pair at position
636 InsertLine(lineInsert
, position
, false);
639 if (breakingUTF8LineEnd
) {
640 RemoveLine(lineInsert
);
642 unsigned char ch
= ' ';
643 for (Sci::Position i
= 0; i
< insertLength
; i
++) {
646 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
648 } else if (ch
== '\n') {
649 if (chPrev
== '\r') {
650 // Patch up what was end of line
651 lv
.SetLineStart(lineInsert
- 1, (position
+ i
) + 1);
653 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
656 } else if (utf8LineEnds
) {
657 const unsigned char back3
[3] = {chBeforePrev
, chPrev
, ch
};
658 if (UTF8IsSeparator(back3
) || UTF8IsNEL(back3
+1)) {
659 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
663 chBeforePrev
= chPrev
;
666 // Joining two lines where last insertion is cr and following substance starts with lf
667 if (chAfter
== '\n') {
669 // End of line already in buffer so drop the newly created one
670 RemoveLine(lineInsert
- 1);
672 } else if (utf8LineEnds
&& !UTF8IsAscii(chAfter
)) {
673 // May have end of UTF-8 line end in buffer and start in insertion
674 for (int j
= 0; j
< UTF8SeparatorLength
-1; j
++) {
675 const unsigned char chAt
= substance
.ValueAt(position
+ insertLength
+ j
);
676 const unsigned char back3
[3] = {chBeforePrev
, chPrev
, chAt
};
677 if (UTF8IsSeparator(back3
)) {
678 InsertLine(lineInsert
, (position
+ insertLength
+ j
) + 1, atLineStart
);
681 if ((j
== 0) && UTF8IsNEL(back3
+1)) {
682 InsertLine(lineInsert
, (position
+ insertLength
+ j
) + 1, atLineStart
);
685 chBeforePrev
= chPrev
;
691 void CellBuffer::BasicDeleteChars(Sci::Position position
, Sci::Position deleteLength
) {
692 if (deleteLength
== 0)
695 if ((position
== 0) && (deleteLength
== substance
.Length())) {
696 // If whole buffer is being deleted, faster to reinitialise lines data
697 // than to delete each line.
700 // Have to fix up line positions before doing deletion as looking at text in buffer
701 // to work out which lines have been removed
703 Sci::Line lineRemove
= lv
.LineFromPosition(position
) + 1;
704 lv
.InsertText(lineRemove
-1, - (deleteLength
));
705 const unsigned char chPrev
= substance
.ValueAt(position
- 1);
706 const unsigned char chBefore
= chPrev
;
707 unsigned char chNext
= substance
.ValueAt(position
);
708 bool ignoreNL
= false;
709 if (chPrev
== '\r' && chNext
== '\n') {
711 lv
.SetLineStart(lineRemove
, position
);
713 ignoreNL
= true; // First \n is not real deletion
715 if (utf8LineEnds
&& UTF8IsTrailByte(chNext
)) {
716 if (UTF8LineEndOverlaps(position
)) {
717 RemoveLine(lineRemove
);
721 unsigned char ch
= chNext
;
722 for (Sci::Position i
= 0; i
< deleteLength
; i
++) {
723 chNext
= substance
.ValueAt(position
+ i
+ 1);
725 if (chNext
!= '\n') {
726 RemoveLine(lineRemove
);
728 } else if (ch
== '\n') {
730 ignoreNL
= false; // Further \n are real deletions
732 RemoveLine(lineRemove
);
734 } else if (utf8LineEnds
) {
735 if (!UTF8IsAscii(ch
)) {
736 const unsigned char next3
[3] = {ch
, chNext
,
737 static_cast<unsigned char>(substance
.ValueAt(position
+ i
+ 2))};
738 if (UTF8IsSeparator(next3
) || UTF8IsNEL(next3
)) {
739 RemoveLine(lineRemove
);
746 // May have to fix up end if last deletion causes cr to be next to lf
747 // or removes one of a crlf pair
748 const char chAfter
= substance
.ValueAt(position
+ deleteLength
);
749 if (chBefore
== '\r' && chAfter
== '\n') {
750 // Using lineRemove-1 as cr ended line before start of deletion
751 RemoveLine(lineRemove
- 1);
752 lv
.SetLineStart(lineRemove
- 1, position
+ 1);
755 substance
.DeleteRange(position
, deleteLength
);
757 style
.DeleteRange(position
, deleteLength
);
761 bool CellBuffer::SetUndoCollection(bool collectUndo
) {
762 collectingUndo
= collectUndo
;
763 uh
.DropUndoSequence();
764 return collectingUndo
;
767 bool CellBuffer::IsCollectingUndo() const {
768 return collectingUndo
;
771 void CellBuffer::BeginUndoAction() {
772 uh
.BeginUndoAction();
775 void CellBuffer::EndUndoAction() {
779 void CellBuffer::AddUndoAction(Sci::Position token
, bool mayCoalesce
) {
781 uh
.AppendAction(containerAction
, token
, 0, 0, startSequence
, mayCoalesce
);
784 void CellBuffer::DeleteUndoHistory() {
785 uh
.DeleteUndoHistory();
788 bool CellBuffer::CanUndo() const {
792 int CellBuffer::StartUndo() {
793 return uh
.StartUndo();
796 const Action
&CellBuffer::GetUndoStep() const {
797 return uh
.GetUndoStep();
800 void CellBuffer::PerformUndoStep() {
801 const Action
&actionStep
= uh
.GetUndoStep();
802 if (actionStep
.at
== insertAction
) {
803 if (substance
.Length() < actionStep
.lenData
) {
804 throw std::runtime_error(
805 "CellBuffer::PerformUndoStep: deletion must be less than document length.");
807 BasicDeleteChars(actionStep
.position
, actionStep
.lenData
);
808 } else if (actionStep
.at
== removeAction
) {
809 BasicInsertString(actionStep
.position
, actionStep
.data
.get(), actionStep
.lenData
);
811 uh
.CompletedUndoStep();
814 bool CellBuffer::CanRedo() const {
818 int CellBuffer::StartRedo() {
819 return uh
.StartRedo();
822 const Action
&CellBuffer::GetRedoStep() const {
823 return uh
.GetRedoStep();
826 void CellBuffer::PerformRedoStep() {
827 const Action
&actionStep
= uh
.GetRedoStep();
828 if (actionStep
.at
== insertAction
) {
829 BasicInsertString(actionStep
.position
, actionStep
.data
.get(), actionStep
.lenData
);
830 } else if (actionStep
.at
== removeAction
) {
831 BasicDeleteChars(actionStep
.position
, actionStep
.lenData
);
833 uh
.CompletedRedoStep();