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.
17 #include "Scintilla.h"
18 #include "SplitVector.h"
19 #include "Partitioning.h"
20 #include "CellBuffer.h"
21 #include "UniConversion.h"
24 using namespace Scintilla
;
27 LineVector::LineVector() : starts(256), perLine(0) {
31 LineVector::~LineVector() {
35 void LineVector::Init() {
42 void LineVector::SetPerLine(PerLine
*pl
) {
46 void LineVector::InsertText(int line
, int delta
) {
47 starts
.InsertText(line
, delta
);
50 void LineVector::InsertLine(int line
, int position
, bool lineStart
) {
51 starts
.InsertPartition(line
, position
);
53 if ((line
> 0) && lineStart
)
55 perLine
->InsertLine(line
);
59 void LineVector::SetLineStart(int line
, int position
) {
60 starts
.SetPartitionStartPosition(line
, position
);
63 void LineVector::RemoveLine(int line
) {
64 starts
.RemovePartition(line
);
66 perLine
->RemoveLine(line
);
70 int LineVector::LineFromPosition(int pos
) const {
71 return starts
.PartitionFromPosition(pos
);
86 void Action::Create(actionType at_
, int position_
, const char *data_
, int lenData_
, bool mayCoalesce_
) {
92 data
= new char[lenData_
];
93 memcpy(data
, data_
, lenData_
);
96 mayCoalesce
= mayCoalesce_
;
99 void Action::Destroy() {
104 void Action::Grab(Action
*source
) {
107 position
= source
->position
;
110 lenData
= source
->lenData
;
111 mayCoalesce
= source
->mayCoalesce
;
113 // Ownership of source data transferred to this
114 source
->position
= 0;
115 source
->at
= startAction
;
118 source
->mayCoalesce
= true;
121 // The undo history stores a sequence of user operations that represent the user's view of the
122 // commands executed on the text.
123 // Each user operation contains a sequence of text insertion and text deletion actions.
124 // All the user operations are stored in a list of individual actions with 'start' actions used
125 // as delimiters between user operations.
126 // Initially there is one start action in the history.
127 // As each action is performed, it is recorded in the history. The action may either become
128 // part of the current user operation or may start a new user operation. If it is to be part of the
129 // current operation, then it overwrites the current last action. If it is to be part of a new
130 // operation, it is appended after the current last action.
131 // After writing the new action, a new start action is appended at the end of the history.
132 // The decision of whether to start a new user operation is based upon two factors. If a
133 // compound operation has been explicitly started by calling BeginUndoAction and no matching
134 // EndUndoAction (these calls nest) has been called, then the action is coalesced into the current
135 // operation. If there is no outstanding BeginUndoAction call then a new operation is started
136 // unless it looks as if the new action is caused by the user typing or deleting a stream of text.
137 // Sequences that look like typing or deletion are coalesced into a single user operation.
139 UndoHistory::UndoHistory() {
142 actions
= new Action
[lenActions
];
145 undoSequenceDepth
= 0;
148 actions
[currentAction
].Create(startAction
);
151 UndoHistory::~UndoHistory() {
156 void UndoHistory::EnsureUndoRoom() {
157 // Have to test that there is room for 2 more actions in the array
158 // as two actions may be created by the calling function
159 if (currentAction
>= (lenActions
- 2)) {
160 // Run out of undo nodes so extend the array
161 int lenActionsNew
= lenActions
* 2;
162 Action
*actionsNew
= new Action
[lenActionsNew
];
163 for (int act
= 0; act
<= currentAction
; act
++)
164 actionsNew
[act
].Grab(&actions
[act
]);
166 lenActions
= lenActionsNew
;
167 actions
= actionsNew
;
171 const char *UndoHistory::AppendAction(actionType at
, int position
, const char *data
, int lengthData
,
172 bool &startSequence
, bool mayCoalesce
) {
174 //Platform::DebugPrintf("%% %d action %d %d %d\n", at, position, lengthData, currentAction);
175 //Platform::DebugPrintf("^ %d action %d %d\n", actions[currentAction - 1].at,
176 // actions[currentAction - 1].position, actions[currentAction - 1].lenData);
177 if (currentAction
< savePoint
) {
180 int oldCurrentAction
= currentAction
;
181 if (currentAction
>= 1) {
182 if (0 == undoSequenceDepth
) {
183 // Top level actions may not always be coalesced
185 const Action
*actPrevious
= &(actions
[currentAction
+ targetAct
]);
186 // Container actions may forward the coalesce state of Scintilla Actions.
187 while ((actPrevious
->at
== containerAction
) && actPrevious
->mayCoalesce
) {
189 actPrevious
= &(actions
[currentAction
+ targetAct
]);
191 // See if current action can be coalesced into previous action
192 // Will work if both are inserts or deletes and position is same
193 if (currentAction
== savePoint
) {
195 } else if (!actions
[currentAction
].mayCoalesce
) {
196 // Not allowed to coalesce if this set
198 } else if (!mayCoalesce
|| !actPrevious
->mayCoalesce
) {
200 } else if (at
== containerAction
|| actions
[currentAction
].at
== containerAction
) {
201 ; // A coalescible containerAction
202 } else if ((at
!= actPrevious
->at
) && (actPrevious
->at
!= startAction
)) {
204 } else if ((at
== insertAction
) &&
205 (position
!= (actPrevious
->position
+ actPrevious
->lenData
))) {
206 // Insertions must be immediately after to coalesce
208 } else if (at
== removeAction
) {
209 if ((lengthData
== 1) || (lengthData
== 2)) {
210 if ((position
+ lengthData
) == actPrevious
->position
) {
212 } else if (position
== actPrevious
->position
) {
215 // Removals must be at same position to coalesce
219 // Removals must be of one character to coalesce
227 // Actions not at top level are always coalesced unless this is after return to top level
228 if (!actions
[currentAction
].mayCoalesce
)
234 startSequence
= oldCurrentAction
!= currentAction
;
235 int actionWithData
= currentAction
;
236 actions
[currentAction
].Create(at
, position
, data
, lengthData
, mayCoalesce
);
238 actions
[currentAction
].Create(startAction
);
239 maxAction
= currentAction
;
240 return actions
[actionWithData
].data
;
243 void UndoHistory::BeginUndoAction() {
245 if (undoSequenceDepth
== 0) {
246 if (actions
[currentAction
].at
!= startAction
) {
248 actions
[currentAction
].Create(startAction
);
249 maxAction
= currentAction
;
251 actions
[currentAction
].mayCoalesce
= false;
256 void UndoHistory::EndUndoAction() {
257 PLATFORM_ASSERT(undoSequenceDepth
> 0);
260 if (0 == undoSequenceDepth
) {
261 if (actions
[currentAction
].at
!= startAction
) {
263 actions
[currentAction
].Create(startAction
);
264 maxAction
= currentAction
;
266 actions
[currentAction
].mayCoalesce
= false;
270 void UndoHistory::DropUndoSequence() {
271 undoSequenceDepth
= 0;
274 void UndoHistory::DeleteUndoHistory() {
275 for (int i
= 1; i
< maxAction
; i
++)
276 actions
[i
].Destroy();
279 actions
[currentAction
].Create(startAction
);
283 void UndoHistory::SetSavePoint() {
284 savePoint
= currentAction
;
287 bool UndoHistory::IsSavePoint() const {
288 return savePoint
== currentAction
;
291 bool UndoHistory::CanUndo() const {
292 return (currentAction
> 0) && (maxAction
> 0);
295 int UndoHistory::StartUndo() {
296 // Drop any trailing startAction
297 if (actions
[currentAction
].at
== startAction
&& currentAction
> 0)
300 // Count the steps in this action
301 int act
= currentAction
;
302 while (actions
[act
].at
!= startAction
&& act
> 0) {
305 return currentAction
- act
;
308 const Action
&UndoHistory::GetUndoStep() const {
309 return actions
[currentAction
];
312 void UndoHistory::CompletedUndoStep() {
316 bool UndoHistory::CanRedo() const {
317 return maxAction
> currentAction
;
320 int UndoHistory::StartRedo() {
321 // Drop any leading startAction
322 if (actions
[currentAction
].at
== startAction
&& currentAction
< maxAction
)
325 // Count the steps in this action
326 int act
= currentAction
;
327 while (actions
[act
].at
!= startAction
&& act
< maxAction
) {
330 return act
- currentAction
;
333 const Action
&UndoHistory::GetRedoStep() const {
334 return actions
[currentAction
];
337 void UndoHistory::CompletedRedoStep() {
341 CellBuffer::CellBuffer() {
344 collectingUndo
= true;
347 CellBuffer::~CellBuffer() {
350 char CellBuffer::CharAt(int position
) const {
351 return substance
.ValueAt(position
);
354 void CellBuffer::GetCharRange(char *buffer
, int position
, int lengthRetrieve
) const {
355 if (lengthRetrieve
< 0)
359 if ((position
+ lengthRetrieve
) > substance
.Length()) {
360 Platform::DebugPrintf("Bad GetCharRange %d for %d of %d\n", position
,
361 lengthRetrieve
, substance
.Length());
364 substance
.GetRange(buffer
, position
, lengthRetrieve
);
367 char CellBuffer::StyleAt(int position
) const {
368 return style
.ValueAt(position
);
371 void CellBuffer::GetStyleRange(unsigned char *buffer
, int position
, int lengthRetrieve
) const {
372 if (lengthRetrieve
< 0)
376 if ((position
+ lengthRetrieve
) > style
.Length()) {
377 Platform::DebugPrintf("Bad GetStyleRange %d for %d of %d\n", position
,
378 lengthRetrieve
, style
.Length());
381 style
.GetRange(reinterpret_cast<char *>(buffer
), position
, lengthRetrieve
);
384 const char *CellBuffer::BufferPointer() {
385 return substance
.BufferPointer();
388 const char *CellBuffer::RangePointer(int position
, int rangeLength
) {
389 return substance
.RangePointer(position
, rangeLength
);
392 int CellBuffer::GapPosition() const {
393 return substance
.GapPosition();
396 // The char* returned is to an allocation owned by the undo history
397 const char *CellBuffer::InsertString(int position
, const char *s
, int insertLength
, bool &startSequence
) {
398 // InsertString and DeleteChars are the bottleneck though which all changes occur
399 const char *data
= s
;
401 if (collectingUndo
) {
402 // Save into the undo/redo stack, but only the characters - not the formatting
403 // This takes up about half load time
404 data
= uh
.AppendAction(insertAction
, position
, s
, insertLength
, startSequence
);
407 BasicInsertString(position
, s
, insertLength
);
412 bool CellBuffer::SetStyleAt(int position
, char styleValue
, char mask
) {
414 char curVal
= style
.ValueAt(position
);
415 if ((curVal
& mask
) != styleValue
) {
416 style
.SetValueAt(position
, static_cast<char>((curVal
& ~mask
) | styleValue
));
423 bool CellBuffer::SetStyleFor(int position
, int lengthStyle
, char styleValue
, char mask
) {
424 bool changed
= false;
425 PLATFORM_ASSERT(lengthStyle
== 0 ||
426 (lengthStyle
> 0 && lengthStyle
+ position
<= style
.Length()));
427 while (lengthStyle
--) {
428 char curVal
= style
.ValueAt(position
);
429 if ((curVal
& mask
) != styleValue
) {
430 style
.SetValueAt(position
, static_cast<char>((curVal
& ~mask
) | styleValue
));
438 // The char* returned is to an allocation owned by the undo history
439 const char *CellBuffer::DeleteChars(int position
, int deleteLength
, bool &startSequence
) {
440 // InsertString and DeleteChars are the bottleneck though which all changes occur
441 PLATFORM_ASSERT(deleteLength
> 0);
442 const char *data
= 0;
444 if (collectingUndo
) {
445 // Save into the undo/redo stack, but only the characters - not the formatting
446 // The gap would be moved to position anyway for the deletion so this doesn't cost extra
447 data
= substance
.RangePointer(position
, deleteLength
);
448 data
= uh
.AppendAction(removeAction
, position
, data
, deleteLength
, startSequence
);
451 BasicDeleteChars(position
, deleteLength
);
456 int CellBuffer::Length() const {
457 return substance
.Length();
460 void CellBuffer::Allocate(int newSize
) {
461 substance
.ReAllocate(newSize
);
462 style
.ReAllocate(newSize
);
465 void CellBuffer::SetLineEndTypes(int utf8LineEnds_
) {
466 if (utf8LineEnds
!= utf8LineEnds_
) {
467 utf8LineEnds
= utf8LineEnds_
;
472 void CellBuffer::SetPerLine(PerLine
*pl
) {
476 int CellBuffer::Lines() const {
480 int CellBuffer::LineStart(int line
) const {
483 else if (line
>= Lines())
486 return lv
.LineStart(line
);
489 bool CellBuffer::IsReadOnly() const {
493 void CellBuffer::SetReadOnly(bool set
) {
497 void CellBuffer::SetSavePoint() {
501 bool CellBuffer::IsSavePoint() const {
502 return uh
.IsSavePoint();
507 void CellBuffer::InsertLine(int line
, int position
, bool lineStart
) {
508 lv
.InsertLine(line
, position
, lineStart
);
511 void CellBuffer::RemoveLine(int line
) {
515 bool CellBuffer::UTF8LineEndOverlaps(int position
) const {
516 unsigned char bytes
[] = {
517 static_cast<unsigned char>(substance
.ValueAt(position
-2)),
518 static_cast<unsigned char>(substance
.ValueAt(position
-1)),
519 static_cast<unsigned char>(substance
.ValueAt(position
)),
520 static_cast<unsigned char>(substance
.ValueAt(position
+1)),
522 return UTF8IsSeparator(bytes
) || UTF8IsSeparator(bytes
+1) || UTF8IsNEL(bytes
+1);
525 void CellBuffer::ResetLineEnds() {
526 // Reinitialize line data -- too much work to preserve
530 int length
= Length();
532 bool atLineStart
= true;
533 lv
.InsertText(lineInsert
-1, length
);
534 unsigned char chBeforePrev
= 0;
535 unsigned char chPrev
= 0;
536 for (int i
= 0; i
< length
; i
++) {
537 unsigned char ch
= substance
.ValueAt(position
+ i
);
539 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
541 } else if (ch
== '\n') {
542 if (chPrev
== '\r') {
543 // Patch up what was end of line
544 lv
.SetLineStart(lineInsert
- 1, (position
+ i
) + 1);
546 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
549 } else if (utf8LineEnds
) {
550 unsigned char back3
[3] = {chBeforePrev
, chPrev
, ch
};
551 if (UTF8IsSeparator(back3
) || UTF8IsNEL(back3
+1)) {
552 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
556 chBeforePrev
= chPrev
;
561 void CellBuffer::BasicInsertString(int position
, const char *s
, int insertLength
) {
562 if (insertLength
== 0)
564 PLATFORM_ASSERT(insertLength
> 0);
566 unsigned char chAfter
= substance
.ValueAt(position
);
567 bool breakingUTF8LineEnd
= false;
568 if (utf8LineEnds
&& UTF8IsTrailByte(chAfter
)) {
569 breakingUTF8LineEnd
= UTF8LineEndOverlaps(position
);
572 substance
.InsertFromArray(position
, s
, 0, insertLength
);
573 style
.InsertValue(position
, insertLength
, 0);
575 int lineInsert
= lv
.LineFromPosition(position
) + 1;
576 bool atLineStart
= lv
.LineStart(lineInsert
-1) == position
;
577 // Point all the lines after the insertion point further along in the buffer
578 lv
.InsertText(lineInsert
-1, insertLength
);
579 unsigned char chBeforePrev
= substance
.ValueAt(position
- 2);
580 unsigned char chPrev
= substance
.ValueAt(position
- 1);
581 if (chPrev
== '\r' && chAfter
== '\n') {
582 // Splitting up a crlf pair at position
583 InsertLine(lineInsert
, position
, false);
586 if (breakingUTF8LineEnd
) {
587 RemoveLine(lineInsert
);
589 unsigned char ch
= ' ';
590 for (int i
= 0; i
< insertLength
; i
++) {
593 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
595 } else if (ch
== '\n') {
596 if (chPrev
== '\r') {
597 // Patch up what was end of line
598 lv
.SetLineStart(lineInsert
- 1, (position
+ i
) + 1);
600 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
603 } else if (utf8LineEnds
) {
604 unsigned char back3
[3] = {chBeforePrev
, chPrev
, ch
};
605 if (UTF8IsSeparator(back3
) || UTF8IsNEL(back3
+1)) {
606 InsertLine(lineInsert
, (position
+ i
) + 1, atLineStart
);
610 chBeforePrev
= chPrev
;
613 // Joining two lines where last insertion is cr and following substance starts with lf
614 if (chAfter
== '\n') {
616 // End of line already in buffer so drop the newly created one
617 RemoveLine(lineInsert
- 1);
619 } else if (utf8LineEnds
&& !UTF8IsAscii(chAfter
)) {
620 // May have end of UTF-8 line end in buffer and start in insertion
621 for (int j
= 0; j
< UTF8SeparatorLength
-1; j
++) {
622 unsigned char chAt
= substance
.ValueAt(position
+ insertLength
+ j
);
623 unsigned char back3
[3] = {chBeforePrev
, chPrev
, chAt
};
624 if (UTF8IsSeparator(back3
)) {
625 InsertLine(lineInsert
, (position
+ insertLength
+ j
) + 1, atLineStart
);
628 if ((j
== 0) && UTF8IsNEL(back3
+1)) {
629 InsertLine(lineInsert
, (position
+ insertLength
+ j
) + 1, atLineStart
);
632 chBeforePrev
= chPrev
;
638 void CellBuffer::BasicDeleteChars(int position
, int deleteLength
) {
639 if (deleteLength
== 0)
642 if ((position
== 0) && (deleteLength
== substance
.Length())) {
643 // If whole buffer is being deleted, faster to reinitialise lines data
644 // than to delete each line.
647 // Have to fix up line positions before doing deletion as looking at text in buffer
648 // to work out which lines have been removed
650 int lineRemove
= lv
.LineFromPosition(position
) + 1;
651 lv
.InsertText(lineRemove
-1, - (deleteLength
));
652 unsigned char chPrev
= substance
.ValueAt(position
- 1);
653 unsigned char chBefore
= chPrev
;
654 unsigned char chNext
= substance
.ValueAt(position
);
655 bool ignoreNL
= false;
656 if (chPrev
== '\r' && chNext
== '\n') {
658 lv
.SetLineStart(lineRemove
, position
);
660 ignoreNL
= true; // First \n is not real deletion
662 if (utf8LineEnds
&& UTF8IsTrailByte(chNext
)) {
663 if (UTF8LineEndOverlaps(position
)) {
664 RemoveLine(lineRemove
);
668 unsigned char ch
= chNext
;
669 for (int i
= 0; i
< deleteLength
; i
++) {
670 chNext
= substance
.ValueAt(position
+ i
+ 1);
672 if (chNext
!= '\n') {
673 RemoveLine(lineRemove
);
675 } else if (ch
== '\n') {
677 ignoreNL
= false; // Further \n are real deletions
679 RemoveLine(lineRemove
);
681 } else if (utf8LineEnds
) {
682 if (!UTF8IsAscii(ch
)) {
683 unsigned char next3
[3] = {ch
, chNext
,
684 static_cast<unsigned char>(substance
.ValueAt(position
+ i
+ 2))};
685 if (UTF8IsSeparator(next3
) || UTF8IsNEL(next3
)) {
686 RemoveLine(lineRemove
);
693 // May have to fix up end if last deletion causes cr to be next to lf
694 // or removes one of a crlf pair
695 char chAfter
= substance
.ValueAt(position
+ deleteLength
);
696 if (chBefore
== '\r' && chAfter
== '\n') {
697 // Using lineRemove-1 as cr ended line before start of deletion
698 RemoveLine(lineRemove
- 1);
699 lv
.SetLineStart(lineRemove
- 1, position
+ 1);
702 substance
.DeleteRange(position
, deleteLength
);
703 style
.DeleteRange(position
, deleteLength
);
706 bool CellBuffer::SetUndoCollection(bool collectUndo
) {
707 collectingUndo
= collectUndo
;
708 uh
.DropUndoSequence();
709 return collectingUndo
;
712 bool CellBuffer::IsCollectingUndo() const {
713 return collectingUndo
;
716 void CellBuffer::BeginUndoAction() {
717 uh
.BeginUndoAction();
720 void CellBuffer::EndUndoAction() {
724 void CellBuffer::AddUndoAction(int token
, bool mayCoalesce
) {
726 uh
.AppendAction(containerAction
, token
, 0, 0, startSequence
, mayCoalesce
);
729 void CellBuffer::DeleteUndoHistory() {
730 uh
.DeleteUndoHistory();
733 bool CellBuffer::CanUndo() const {
737 int CellBuffer::StartUndo() {
738 return uh
.StartUndo();
741 const Action
&CellBuffer::GetUndoStep() const {
742 return uh
.GetUndoStep();
745 void CellBuffer::PerformUndoStep() {
746 const Action
&actionStep
= uh
.GetUndoStep();
747 if (actionStep
.at
== insertAction
) {
748 BasicDeleteChars(actionStep
.position
, actionStep
.lenData
);
749 } else if (actionStep
.at
== removeAction
) {
750 BasicInsertString(actionStep
.position
, actionStep
.data
, actionStep
.lenData
);
752 uh
.CompletedUndoStep();
755 bool CellBuffer::CanRedo() const {
759 int CellBuffer::StartRedo() {
760 return uh
.StartRedo();
763 const Action
&CellBuffer::GetRedoStep() const {
764 return uh
.GetRedoStep();
767 void CellBuffer::PerformRedoStep() {
768 const Action
&actionStep
= uh
.GetRedoStep();
769 if (actionStep
.at
== insertAction
) {
770 BasicInsertString(actionStep
.position
, actionStep
.data
, actionStep
.lenData
);
771 } else if (actionStep
.at
== removeAction
) {
772 BasicDeleteChars(actionStep
.position
, actionStep
.lenData
);
774 uh
.CompletedRedoStep();