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.
18 #include "Scintilla.h"
20 #include "SplitVector.h"
21 #include "Partitioning.h"
22 #include "CellBuffer.h"
23 #include "UniConversion.h"
26 using namespace Scintilla
;
29 LineVector::LineVector() : starts(256), perLine(0) {
33 LineVector::~LineVector() {
37 void LineVector::Init() {
44 void LineVector::SetPerLine(PerLine
*pl
) {
48 void LineVector::InsertText(int line
, int delta
) {
49 starts
.InsertText(line
, delta
);
52 void LineVector::InsertLine(int line
, int position
, bool lineStart
) {
53 starts
.InsertPartition(line
, position
);
55 if ((line
> 0) && lineStart
)
57 perLine
->InsertLine(line
);
61 void LineVector::SetLineStart(int line
, int position
) {
62 starts
.SetPartitionStartPosition(line
, position
);
65 void LineVector::RemoveLine(int line
) {
66 starts
.RemovePartition(line
);
68 perLine
->RemoveLine(line
);
72 int LineVector::LineFromPosition(int pos
) const {
73 return starts
.PartitionFromPosition(pos
);
88 void Action::Create(actionType at_
, int position_
, const char *data_
, int lenData_
, bool mayCoalesce_
) {
94 data
= new char[lenData_
];
95 memcpy(data
, data_
, lenData_
);
98 mayCoalesce
= mayCoalesce_
;
101 void Action::Destroy() {
106 void Action::Grab(Action
*source
) {
109 position
= source
->position
;
112 lenData
= source
->lenData
;
113 mayCoalesce
= source
->mayCoalesce
;
115 // Ownership of source data transferred to this
116 source
->position
= 0;
117 source
->at
= startAction
;
120 source
->mayCoalesce
= true;
123 // The undo history stores a sequence of user operations that represent the user's view of the
124 // commands executed on the text.
125 // Each user operation contains a sequence of text insertion and text deletion actions.
126 // All the user operations are stored in a list of individual actions with 'start' actions used
127 // as delimiters between user operations.
128 // Initially there is one start action in the history.
129 // As each action is performed, it is recorded in the history. The action may either become
130 // part of the current user operation or may start a new user operation. If it is to be part of the
131 // current operation, then it overwrites the current last action. If it is to be part of a new
132 // operation, it is appended after the current last action.
133 // After writing the new action, a new start action is appended at the end of the history.
134 // The decision of whether to start a new user operation is based upon two factors. If a
135 // compound operation has been explicitly started by calling BeginUndoAction and no matching
136 // EndUndoAction (these calls nest) has been called, then the action is coalesced into the current
137 // operation. If there is no outstanding BeginUndoAction call then a new operation is started
138 // unless it looks as if the new action is caused by the user typing or deleting a stream of text.
139 // Sequences that look like typing or deletion are coalesced into a single user operation.
141 UndoHistory::UndoHistory() {
144 actions
= new Action
[lenActions
];
147 undoSequenceDepth
= 0;
151 actions
[currentAction
].Create(startAction
);
154 UndoHistory::~UndoHistory() {
159 void UndoHistory::EnsureUndoRoom() {
160 // Have to test that there is room for 2 more actions in the array
161 // as two actions may be created by the calling function
162 if (currentAction
>= (lenActions
- 2)) {
163 // Run out of undo nodes so extend the array
164 int lenActionsNew
= lenActions
* 2;
165 Action
*actionsNew
= new Action
[lenActionsNew
];
166 for (int act
= 0; act
<= currentAction
; act
++)
167 actionsNew
[act
].Grab(&actions
[act
]);
169 lenActions
= lenActionsNew
;
170 actions
= actionsNew
;
174 const char *UndoHistory::AppendAction(actionType at
, int position
, const char *data
, int lengthData
,
175 bool &startSequence
, bool mayCoalesce
) {
177 //Platform::DebugPrintf("%% %d action %d %d %d\n", at, position, lengthData, currentAction);
178 //Platform::DebugPrintf("^ %d action %d %d\n", actions[currentAction - 1].at,
179 // actions[currentAction - 1].position, actions[currentAction - 1].lenData);
180 if (currentAction
< savePoint
) {
183 int oldCurrentAction
= currentAction
;
184 if (currentAction
>= 1) {
185 if (0 == undoSequenceDepth
) {
186 // Top level actions may not always be coalesced
188 const Action
*actPrevious
= &(actions
[currentAction
+ targetAct
]);
189 // Container actions may forward the coalesce state of Scintilla Actions.
190 while ((actPrevious
->at
== containerAction
) && actPrevious
->mayCoalesce
) {
192 actPrevious
= &(actions
[currentAction
+ targetAct
]);
194 // See if current action can be coalesced into previous action
195 // Will work if both are inserts or deletes and position is same
196 #if defined(_MSC_VER) && defined(_PREFAST_)
197 // Visual Studio 2013 Code Analysis wrongly believes actions can be NULL at its next reference
198 __analysis_assume(actions
);
200 if ((currentAction
== savePoint
) || (currentAction
== tentativePoint
)) {
202 } else if (!actions
[currentAction
].mayCoalesce
) {
203 // Not allowed to coalesce if this set
205 } else if (!mayCoalesce
|| !actPrevious
->mayCoalesce
) {
207 } else if (at
== containerAction
|| actions
[currentAction
].at
== containerAction
) {
208 ; // A coalescible containerAction
209 } else if ((at
!= actPrevious
->at
) && (actPrevious
->at
!= startAction
)) {
211 } else if ((at
== insertAction
) &&
212 (position
!= (actPrevious
->position
+ actPrevious
->lenData
))) {
213 // Insertions must be immediately after to coalesce
215 } else if (at
== removeAction
) {
216 if ((lengthData
== 1) || (lengthData
== 2)) {
217 if ((position
+ lengthData
) == actPrevious
->position
) {
219 } else if (position
== actPrevious
->position
) {
222 // Removals must be at same position to coalesce
226 // Removals must be of one character to coalesce
234 // Actions not at top level are always coalesced unless this is after return to top level
235 if (!actions
[currentAction
].mayCoalesce
)
241 startSequence
= oldCurrentAction
!= currentAction
;
242 int actionWithData
= currentAction
;
243 actions
[currentAction
].Create(at
, position
, data
, lengthData
, mayCoalesce
);
245 actions
[currentAction
].Create(startAction
);
246 maxAction
= currentAction
;
247 return actions
[actionWithData
].data
;
250 void UndoHistory::BeginUndoAction() {
252 if (undoSequenceDepth
== 0) {
253 if (actions
[currentAction
].at
!= startAction
) {
255 actions
[currentAction
].Create(startAction
);
256 maxAction
= currentAction
;
258 actions
[currentAction
].mayCoalesce
= false;
263 void UndoHistory::EndUndoAction() {
264 PLATFORM_ASSERT(undoSequenceDepth
> 0);
267 if (0 == undoSequenceDepth
) {
268 if (actions
[currentAction
].at
!= startAction
) {
270 actions
[currentAction
].Create(startAction
);
271 maxAction
= currentAction
;
273 actions
[currentAction
].mayCoalesce
= false;
277 void UndoHistory::DropUndoSequence() {
278 undoSequenceDepth
= 0;
281 void UndoHistory::DeleteUndoHistory() {
282 for (int i
= 1; i
< maxAction
; i
++)
283 actions
[i
].Destroy();
286 actions
[currentAction
].Create(startAction
);
291 void UndoHistory::SetSavePoint() {
292 savePoint
= currentAction
;
295 bool UndoHistory::IsSavePoint() const {
296 return savePoint
== currentAction
;
299 void UndoHistory::TentativeStart() {
300 tentativePoint
= currentAction
;
303 void UndoHistory::TentativeCommit() {
305 // Truncate undo history
306 maxAction
= currentAction
;
309 int UndoHistory::TentativeSteps() {
310 // Drop any trailing startAction
311 if (actions
[currentAction
].at
== startAction
&& currentAction
> 0)
313 if (tentativePoint
>= 0)
314 return currentAction
- tentativePoint
;
319 bool UndoHistory::CanUndo() const {
320 return (currentAction
> 0) && (maxAction
> 0);
323 int UndoHistory::StartUndo() {
324 // Drop any trailing startAction
325 if (actions
[currentAction
].at
== startAction
&& currentAction
> 0)
328 // Count the steps in this action
329 int act
= currentAction
;
330 while (actions
[act
].at
!= startAction
&& act
> 0) {
333 return currentAction
- act
;
336 const Action
&UndoHistory::GetUndoStep() const {
337 return actions
[currentAction
];
340 void UndoHistory::CompletedUndoStep() {
344 bool UndoHistory::CanRedo() const {
345 return maxAction
> currentAction
;
348 int UndoHistory::StartRedo() {
349 // Drop any leading startAction
350 if (actions
[currentAction
].at
== startAction
&& currentAction
< maxAction
)
353 // Count the steps in this action
354 int act
= currentAction
;
355 while (actions
[act
].at
!= startAction
&& act
< maxAction
) {
358 return act
- currentAction
;
361 const Action
&UndoHistory::GetRedoStep() const {
362 return actions
[currentAction
];
365 void UndoHistory::CompletedRedoStep() {
369 CellBuffer::CellBuffer() {
372 collectingUndo
= true;
375 CellBuffer::~CellBuffer() {
378 char CellBuffer::CharAt(int position
) const {
379 return substance
.ValueAt(position
);
382 void CellBuffer::GetCharRange(char *buffer
, int position
, int lengthRetrieve
) const {
383 if (lengthRetrieve
<= 0)
387 if ((position
+ lengthRetrieve
) > substance
.Length()) {
388 Platform::DebugPrintf("Bad GetCharRange %d for %d of %d\n", position
,
389 lengthRetrieve
, substance
.Length());
392 substance
.GetRange(buffer
, position
, lengthRetrieve
);
395 char CellBuffer::StyleAt(int position
) const {
396 return style
.ValueAt(position
);
399 void CellBuffer::GetStyleRange(unsigned char *buffer
, int position
, int lengthRetrieve
) const {
400 if (lengthRetrieve
< 0)
404 if ((position
+ lengthRetrieve
) > style
.Length()) {
405 Platform::DebugPrintf("Bad GetStyleRange %d for %d of %d\n", position
,
406 lengthRetrieve
, style
.Length());
409 style
.GetRange(reinterpret_cast<char *>(buffer
), position
, lengthRetrieve
);
412 const char *CellBuffer::BufferPointer() {
413 return substance
.BufferPointer();
416 const char *CellBuffer::RangePointer(int position
, int rangeLength
) {
417 return substance
.RangePointer(position
, rangeLength
);
420 int CellBuffer::GapPosition() const {
421 return substance
.GapPosition();
424 // The char* returned is to an allocation owned by the undo history
425 const char *CellBuffer::InsertString(int position
, const char *s
, int insertLength
, bool &startSequence
) {
426 // InsertString and DeleteChars are the bottleneck though which all changes occur
427 const char *data
= s
;
429 if (collectingUndo
) {
430 // Save into the undo/redo stack, but only the characters - not the formatting
431 // This takes up about half load time
432 data
= uh
.AppendAction(insertAction
, position
, s
, insertLength
, startSequence
);
435 BasicInsertString(position
, s
, insertLength
);
440 bool CellBuffer::SetStyleAt(int position
, char styleValue
) {
441 char curVal
= style
.ValueAt(position
);
442 if (curVal
!= styleValue
) {
443 style
.SetValueAt(position
, styleValue
);
450 bool CellBuffer::SetStyleFor(int position
, int lengthStyle
, char styleValue
) {
451 bool changed
= false;
452 PLATFORM_ASSERT(lengthStyle
== 0 ||
453 (lengthStyle
> 0 && lengthStyle
+ position
<= style
.Length()));
454 while (lengthStyle
--) {
455 char curVal
= style
.ValueAt(position
);
456 if (curVal
!= styleValue
) {
457 style
.SetValueAt(position
, styleValue
);
465 // The char* returned is to an allocation owned by the undo history
466 const char *CellBuffer::DeleteChars(int position
, int deleteLength
, bool &startSequence
) {
467 // InsertString and DeleteChars are the bottleneck though which all changes occur
468 PLATFORM_ASSERT(deleteLength
> 0);
469 const char *data
= 0;
471 if (collectingUndo
) {
472 // Save into the undo/redo stack, but only the characters - not the formatting
473 // The gap would be moved to position anyway for the deletion so this doesn't cost extra
474 data
= substance
.RangePointer(position
, deleteLength
);
475 data
= uh
.AppendAction(removeAction
, position
, data
, deleteLength
, startSequence
);
478 BasicDeleteChars(position
, deleteLength
);
483 int CellBuffer::Length() const {
484 return substance
.Length();
487 void CellBuffer::Allocate(int newSize
) {
488 substance
.ReAllocate(newSize
);
489 style
.ReAllocate(newSize
);
492 void CellBuffer::SetLineEndTypes(int utf8LineEnds_
) {
493 if (utf8LineEnds
!= utf8LineEnds_
) {
494 utf8LineEnds
= utf8LineEnds_
;
499 bool CellBuffer::ContainsLineEnd(const char *s
, int length
) const {
500 unsigned char chBeforePrev
= 0;
501 unsigned char chPrev
= 0;
502 for (int i
= 0; i
< length
; i
++) {
503 const unsigned char ch
= s
[i
];
504 if ((ch
== '\r') || (ch
== '\n')) {
506 } else if (utf8LineEnds
) {
507 unsigned char back3
[3] = { chBeforePrev
, chPrev
, ch
};
508 if (UTF8IsSeparator(back3
) || UTF8IsNEL(back3
+ 1)) {
512 chBeforePrev
= chPrev
;
518 void CellBuffer::SetPerLine(PerLine
*pl
) {
522 int CellBuffer::Lines() const {
526 int CellBuffer::LineStart(int line
) const {
529 else if (line
>= Lines())
532 return lv
.LineStart(line
);
535 bool CellBuffer::IsReadOnly() const {
539 void CellBuffer::SetReadOnly(bool set
) {
543 void CellBuffer::SetSavePoint() {
547 bool CellBuffer::IsSavePoint() const {
548 return uh
.IsSavePoint();
551 void CellBuffer::TentativeStart() {
555 void CellBuffer::TentativeCommit() {
556 uh
.TentativeCommit();
559 int CellBuffer::TentativeSteps() {
560 return uh
.TentativeSteps();
563 bool CellBuffer::TentativeActive() const {
564 return uh
.TentativeActive();
569 void CellBuffer::InsertLine(int line
, int position
, bool lineStart
) {
570 lv
.InsertLine(line
, position
, lineStart
);
573 void CellBuffer::RemoveLine(int line
) {
577 bool CellBuffer::UTF8LineEndOverlaps(int position
) const {
578 unsigned char bytes
[] = {
579 static_cast<unsigned char>(substance
.ValueAt(position
-2)),
580 static_cast<unsigned char>(substance
.ValueAt(position
-1)),
581 static_cast<unsigned char>(substance
.ValueAt(position
)),
582 static_cast<unsigned char>(substance
.ValueAt(position
+1)),
584 return UTF8IsSeparator(bytes
) || UTF8IsSeparator(bytes
+1) || UTF8IsNEL(bytes
+1);
587 void CellBuffer::ResetLineEnds() {
588 // Reinitialize line data -- too much work to preserve
592 int length
= Length();
594 bool atLineStart
= true;
595 lv
.InsertText(lineInsert
-1, length
);
596 unsigned char chBeforePrev
= 0;
597 unsigned char chPrev
= 0;
598 for (int i
= 0; i
< length
; i
++) {
599 unsigned char ch
= substance
.ValueAt(position
+ i
);
601 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
603 } else if (ch
== '\n') {
604 if (chPrev
== '\r') {
605 // Patch up what was end of line
606 lv
.SetLineStart(lineInsert
- 1, (position
+ i
) + 1);
608 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
611 } else if (utf8LineEnds
) {
612 unsigned char back3
[3] = {chBeforePrev
, chPrev
, ch
};
613 if (UTF8IsSeparator(back3
) || UTF8IsNEL(back3
+1)) {
614 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
618 chBeforePrev
= chPrev
;
623 void CellBuffer::BasicInsertString(int position
, const char *s
, int insertLength
) {
624 if (insertLength
== 0)
626 PLATFORM_ASSERT(insertLength
> 0);
628 unsigned char chAfter
= substance
.ValueAt(position
);
629 bool breakingUTF8LineEnd
= false;
630 if (utf8LineEnds
&& UTF8IsTrailByte(chAfter
)) {
631 breakingUTF8LineEnd
= UTF8LineEndOverlaps(position
);
634 substance
.InsertFromArray(position
, s
, 0, insertLength
);
635 style
.InsertValue(position
, insertLength
, 0);
637 int lineInsert
= lv
.LineFromPosition(position
) + 1;
638 bool atLineStart
= lv
.LineStart(lineInsert
-1) == position
;
639 // Point all the lines after the insertion point further along in the buffer
640 lv
.InsertText(lineInsert
-1, insertLength
);
641 unsigned char chBeforePrev
= substance
.ValueAt(position
- 2);
642 unsigned char chPrev
= substance
.ValueAt(position
- 1);
643 if (chPrev
== '\r' && chAfter
== '\n') {
644 // Splitting up a crlf pair at position
645 InsertLine(lineInsert
, position
, false);
648 if (breakingUTF8LineEnd
) {
649 RemoveLine(lineInsert
);
651 unsigned char ch
= ' ';
652 for (int i
= 0; i
< insertLength
; i
++) {
655 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
657 } else if (ch
== '\n') {
658 if (chPrev
== '\r') {
659 // Patch up what was end of line
660 lv
.SetLineStart(lineInsert
- 1, (position
+ i
) + 1);
662 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
665 } else if (utf8LineEnds
) {
666 unsigned char back3
[3] = {chBeforePrev
, chPrev
, ch
};
667 if (UTF8IsSeparator(back3
) || UTF8IsNEL(back3
+1)) {
668 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
672 chBeforePrev
= chPrev
;
675 // Joining two lines where last insertion is cr and following substance starts with lf
676 if (chAfter
== '\n') {
678 // End of line already in buffer so drop the newly created one
679 RemoveLine(lineInsert
- 1);
681 } else if (utf8LineEnds
&& !UTF8IsAscii(chAfter
)) {
682 // May have end of UTF-8 line end in buffer and start in insertion
683 for (int j
= 0; j
< UTF8SeparatorLength
-1; j
++) {
684 unsigned char chAt
= substance
.ValueAt(position
+ insertLength
+ j
);
685 unsigned char back3
[3] = {chBeforePrev
, chPrev
, chAt
};
686 if (UTF8IsSeparator(back3
)) {
687 InsertLine(lineInsert
, (position
+ insertLength
+ j
) + 1, atLineStart
);
690 if ((j
== 0) && UTF8IsNEL(back3
+1)) {
691 InsertLine(lineInsert
, (position
+ insertLength
+ j
) + 1, atLineStart
);
694 chBeforePrev
= chPrev
;
700 void CellBuffer::BasicDeleteChars(int position
, int deleteLength
) {
701 if (deleteLength
== 0)
704 if ((position
== 0) && (deleteLength
== substance
.Length())) {
705 // If whole buffer is being deleted, faster to reinitialise lines data
706 // than to delete each line.
709 // Have to fix up line positions before doing deletion as looking at text in buffer
710 // to work out which lines have been removed
712 int lineRemove
= lv
.LineFromPosition(position
) + 1;
713 lv
.InsertText(lineRemove
-1, - (deleteLength
));
714 unsigned char chPrev
= substance
.ValueAt(position
- 1);
715 unsigned char chBefore
= chPrev
;
716 unsigned char chNext
= substance
.ValueAt(position
);
717 bool ignoreNL
= false;
718 if (chPrev
== '\r' && chNext
== '\n') {
720 lv
.SetLineStart(lineRemove
, position
);
722 ignoreNL
= true; // First \n is not real deletion
724 if (utf8LineEnds
&& UTF8IsTrailByte(chNext
)) {
725 if (UTF8LineEndOverlaps(position
)) {
726 RemoveLine(lineRemove
);
730 unsigned char ch
= chNext
;
731 for (int i
= 0; i
< deleteLength
; i
++) {
732 chNext
= substance
.ValueAt(position
+ i
+ 1);
734 if (chNext
!= '\n') {
735 RemoveLine(lineRemove
);
737 } else if (ch
== '\n') {
739 ignoreNL
= false; // Further \n are real deletions
741 RemoveLine(lineRemove
);
743 } else if (utf8LineEnds
) {
744 if (!UTF8IsAscii(ch
)) {
745 unsigned char next3
[3] = {ch
, chNext
,
746 static_cast<unsigned char>(substance
.ValueAt(position
+ i
+ 2))};
747 if (UTF8IsSeparator(next3
) || UTF8IsNEL(next3
)) {
748 RemoveLine(lineRemove
);
755 // May have to fix up end if last deletion causes cr to be next to lf
756 // or removes one of a crlf pair
757 char chAfter
= substance
.ValueAt(position
+ deleteLength
);
758 if (chBefore
== '\r' && chAfter
== '\n') {
759 // Using lineRemove-1 as cr ended line before start of deletion
760 RemoveLine(lineRemove
- 1);
761 lv
.SetLineStart(lineRemove
- 1, position
+ 1);
764 substance
.DeleteRange(position
, deleteLength
);
765 style
.DeleteRange(position
, deleteLength
);
768 bool CellBuffer::SetUndoCollection(bool collectUndo
) {
769 collectingUndo
= collectUndo
;
770 uh
.DropUndoSequence();
771 return collectingUndo
;
774 bool CellBuffer::IsCollectingUndo() const {
775 return collectingUndo
;
778 void CellBuffer::BeginUndoAction() {
779 uh
.BeginUndoAction();
782 void CellBuffer::EndUndoAction() {
786 void CellBuffer::AddUndoAction(int token
, bool mayCoalesce
) {
788 uh
.AppendAction(containerAction
, token
, 0, 0, startSequence
, mayCoalesce
);
791 void CellBuffer::DeleteUndoHistory() {
792 uh
.DeleteUndoHistory();
795 bool CellBuffer::CanUndo() const {
799 int CellBuffer::StartUndo() {
800 return uh
.StartUndo();
803 const Action
&CellBuffer::GetUndoStep() const {
804 return uh
.GetUndoStep();
807 void CellBuffer::PerformUndoStep() {
808 const Action
&actionStep
= uh
.GetUndoStep();
809 if (actionStep
.at
== insertAction
) {
810 if (substance
.Length() < actionStep
.lenData
) {
811 throw std::runtime_error(
812 "CellBuffer::PerformUndoStep: deletion must be less than document length.");
814 BasicDeleteChars(actionStep
.position
, actionStep
.lenData
);
815 } else if (actionStep
.at
== removeAction
) {
816 BasicInsertString(actionStep
.position
, actionStep
.data
, actionStep
.lenData
);
818 uh
.CompletedUndoStep();
821 bool CellBuffer::CanRedo() const {
825 int CellBuffer::StartRedo() {
826 return uh
.StartRedo();
829 const Action
&CellBuffer::GetRedoStep() const {
830 return uh
.GetRedoStep();
833 void CellBuffer::PerformRedoStep() {
834 const Action
&actionStep
= uh
.GetRedoStep();
835 if (actionStep
.at
== insertAction
) {
836 BasicInsertString(actionStep
.position
, actionStep
.data
, actionStep
.lenData
);
837 } else if (actionStep
.at
== removeAction
) {
838 BasicDeleteChars(actionStep
.position
, actionStep
.lenData
);
840 uh
.CompletedRedoStep();