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.
15 #include "Scintilla.h"
16 #include "SplitVector.h"
17 #include "Partitioning.h"
18 #include "CellBuffer.h"
21 using namespace Scintilla
;
24 MarkerHandleSet::MarkerHandleSet() {
28 MarkerHandleSet::~MarkerHandleSet() {
29 MarkerHandleNumber
*mhn
= root
;
31 MarkerHandleNumber
*mhnToFree
= mhn
;
38 int MarkerHandleSet::Length() const {
40 MarkerHandleNumber
*mhn
= root
;
48 int MarkerHandleSet::NumberFromHandle(int handle
) const {
49 MarkerHandleNumber
*mhn
= root
;
51 if (mhn
->handle
== handle
) {
59 int MarkerHandleSet::MarkValue() const {
61 MarkerHandleNumber
*mhn
= root
;
63 m
|= (1 << mhn
->number
);
69 bool MarkerHandleSet::Contains(int handle
) const {
70 MarkerHandleNumber
*mhn
= root
;
72 if (mhn
->handle
== handle
) {
80 bool MarkerHandleSet::InsertHandle(int handle
, int markerNum
) {
81 MarkerHandleNumber
*mhn
= new MarkerHandleNumber
;
85 mhn
->number
= markerNum
;
91 void MarkerHandleSet::RemoveHandle(int handle
) {
92 MarkerHandleNumber
**pmhn
= &root
;
94 MarkerHandleNumber
*mhn
= *pmhn
;
95 if (mhn
->handle
== handle
) {
100 pmhn
= &((*pmhn
)->next
);
104 bool MarkerHandleSet::RemoveNumber(int markerNum
) {
105 bool performedDeletion
= false;
106 MarkerHandleNumber
**pmhn
= &root
;
108 MarkerHandleNumber
*mhn
= *pmhn
;
109 if (mhn
->number
== markerNum
) {
112 performedDeletion
= true;
114 pmhn
= &((*pmhn
)->next
);
117 return performedDeletion
;
120 void MarkerHandleSet::CombineWith(MarkerHandleSet
*other
) {
121 MarkerHandleNumber
**pmhn
= &root
;
123 pmhn
= &((*pmhn
)->next
);
129 LineVector::LineVector() : starts(256) {
135 LineVector::~LineVector() {
137 for (int line
= 0; line
< markers
.Length(); line
++) {
138 delete markers
[line
];
145 void LineVector::Init() {
147 for (int line
= 0; line
< markers
.Length(); line
++) {
148 delete markers
[line
];
155 void LineVector::ExpandLevels(int sizeNew
) {
156 levels
.InsertValue(levels
.Length(), sizeNew
- levels
.Length(), SC_FOLDLEVELBASE
);
159 void LineVector::ClearLevels() {
163 int LineVector::SetLevel(int line
, int level
) {
165 if ((line
>= 0) && (line
< Lines())) {
166 if (!levels
.Length()) {
167 ExpandLevels(Lines() + 1);
171 levels
[line
] = level
;
177 int LineVector::GetLevel(int line
) {
178 if (levels
.Length() && (line
>= 0) && (line
< Lines())) {
181 return SC_FOLDLEVELBASE
;
185 void LineVector::InsertText(int line
, int delta
) {
186 starts
.InsertText(line
, delta
);
189 void LineVector::InsertLine(int line
, int position
) {
190 starts
.InsertPartition(line
, position
);
191 if (markers
.Length()) {
192 markers
.Insert(line
, 0);
194 if (levels
.Length()) {
195 int level
= SC_FOLDLEVELBASE
;
196 if ((line
> 0) && (line
< Lines())) {
197 level
= levels
[line
-1] & ~SC_FOLDLEVELWHITEFLAG
;
199 levels
.InsertValue(line
, 1, level
);
203 void LineVector::SetLineStart(int line
, int position
) {
204 starts
.SetPartitionStartPosition(line
, position
);
207 void LineVector::RemoveLine(int line
) {
208 starts
.RemovePartition(line
);
209 // Retain the markers from the deleted line by oring them into the previous line
210 if (markers
.Length()) {
212 MergeMarkers(line
- 1);
214 markers
.Delete(line
);
216 if (levels
.Length()) {
217 // Move up following lines but merge header flag from this line
218 // to line before to avoid a temporary disappearence causing expansion.
219 int firstHeader
= levels
[line
] & SC_FOLDLEVELHEADERFLAG
;
222 levels
[line
-1] |= firstHeader
;
226 int LineVector::LineFromPosition(int pos
) {
227 return starts
.PartitionFromPosition(pos
);
230 int LineVector::MarkValue(int line
) {
231 if (markers
.Length() && markers
[line
])
232 return markers
[line
]->MarkValue();
237 int LineVector::AddMark(int line
, int markerNum
) {
239 if (!markers
.Length()) {
240 // No existing markers so allocate one element per line
241 markers
.InsertValue(0, Lines(), 0);
243 if (!markers
[line
]) {
244 // Need new structure to hold marker handle
245 markers
[line
] = new MarkerHandleSet();
249 markers
[line
]->InsertHandle(handleCurrent
, markerNum
);
251 return handleCurrent
;
254 void LineVector::MergeMarkers(int pos
) {
255 if (markers
[pos
+ 1] != NULL
) {
256 if (markers
[pos
] == NULL
)
257 markers
[pos
] = new MarkerHandleSet
;
258 markers
[pos
]->CombineWith(markers
[pos
+ 1]);
259 delete markers
[pos
+ 1];
260 markers
[pos
+ 1] = NULL
;
264 void LineVector::DeleteMark(int line
, int markerNum
, bool all
) {
265 if (markers
.Length() && markers
[line
]) {
266 if (markerNum
== -1) {
267 delete markers
[line
];
268 markers
[line
] = NULL
;
270 bool performedDeletion
= markers
[line
]->RemoveNumber(markerNum
);
271 while (all
&& performedDeletion
) {
272 performedDeletion
= markers
[line
]->RemoveNumber(markerNum
);
274 if (markers
[line
]->Length() == 0) {
275 delete markers
[line
];
276 markers
[line
] = NULL
;
282 void LineVector::DeleteMarkFromHandle(int markerHandle
) {
283 int line
= LineFromHandle(markerHandle
);
285 markers
[line
]->RemoveHandle(markerHandle
);
286 if (markers
[line
]->Length() == 0) {
287 delete markers
[line
];
288 markers
[line
] = NULL
;
293 int LineVector::LineFromHandle(int markerHandle
) {
294 if (markers
.Length()) {
295 for (int line
= 0; line
< Lines(); line
++) {
297 if (markers
[line
]->Contains(markerHandle
)) {
317 void Action::Create(actionType at_
, int position_
, char *data_
, int lenData_
, bool mayCoalesce_
) {
319 position
= position_
;
323 mayCoalesce
= mayCoalesce_
;
326 void Action::Destroy() {
331 void Action::Grab(Action
*source
) {
334 position
= source
->position
;
337 lenData
= source
->lenData
;
338 mayCoalesce
= source
->mayCoalesce
;
340 // Ownership of source data transferred to this
341 source
->position
= 0;
342 source
->at
= startAction
;
345 source
->mayCoalesce
= true;
348 // The undo history stores a sequence of user operations that represent the user's view of the
349 // commands executed on the text.
350 // Each user operation contains a sequence of text insertion and text deletion actions.
351 // All the user operations are stored in a list of individual actions with 'start' actions used
352 // as delimiters between user operations.
353 // Initially there is one start action in the history.
354 // As each action is performed, it is recorded in the history. The action may either become
355 // part of the current user operation or may start a new user operation. If it is to be part of the
356 // current operation, then it overwrites the current last action. If it is to be part of a new
357 // operation, it is appended after the current last action.
358 // After writing the new action, a new start action is appended at the end of the history.
359 // The decision of whether to start a new user operation is based upon two factors. If a
360 // compound operation has been explicitly started by calling BeginUndoAction and no matching
361 // EndUndoAction (these calls nest) has been called, then the action is coalesced into the current
362 // operation. If there is no outstanding BeginUndoAction call then a new operation is started
363 // unless it looks as if the new action is caused by the user typing or deleting a stream of text.
364 // Sequences that look like typing or deletion are coalesced into a single user operation.
366 UndoHistory::UndoHistory() {
369 actions
= new Action
[lenActions
];
372 undoSequenceDepth
= 0;
375 actions
[currentAction
].Create(startAction
);
378 UndoHistory::~UndoHistory() {
383 void UndoHistory::EnsureUndoRoom() {
384 // Have to test that there is room for 2 more actions in the array
385 // as two actions may be created by the calling function
386 if (currentAction
>= (lenActions
- 2)) {
387 // Run out of undo nodes so extend the array
388 int lenActionsNew
= lenActions
* 2;
389 Action
*actionsNew
= new Action
[lenActionsNew
];
392 for (int act
= 0; act
<= currentAction
; act
++)
393 actionsNew
[act
].Grab(&actions
[act
]);
395 lenActions
= lenActionsNew
;
396 actions
= actionsNew
;
400 void UndoHistory::AppendAction(actionType at
, int position
, char *data
, int lengthData
,
401 bool &startSequence
) {
403 //Platform::DebugPrintf("%% %d action %d %d %d\n", at, position, lengthData, currentAction);
404 //Platform::DebugPrintf("^ %d action %d %d\n", actions[currentAction - 1].at,
405 // actions[currentAction - 1].position, actions[currentAction - 1].lenData);
406 if (currentAction
< savePoint
) {
409 int oldCurrentAction
= currentAction
;
410 if (currentAction
>= 1) {
411 if (0 == undoSequenceDepth
) {
412 // Top level actions may not always be coalesced
413 Action
&actPrevious
= actions
[currentAction
- 1];
414 // See if current action can be coalesced into previous action
415 // Will work if both are inserts or deletes and position is same
416 if (at
!= actPrevious
.at
) {
418 } else if (currentAction
== savePoint
) {
420 } else if ((at
== insertAction
) &&
421 (position
!= (actPrevious
.position
+ actPrevious
.lenData
))) {
422 // Insertions must be immediately after to coalesce
424 } else if (!actions
[currentAction
].mayCoalesce
) {
425 // Not allowed to coalesce if this set
427 } else if (at
== removeAction
) {
428 if ((lengthData
== 1) || (lengthData
== 2)){
429 if ((position
+ lengthData
) == actPrevious
.position
) {
431 } else if (position
== actPrevious
.position
) {
434 // Removals must be at same position to coalesce
438 // Removals must be of one character to coalesce
446 // Actions not at top level are always coalesced unless this is after return to top level
447 if (!actions
[currentAction
].mayCoalesce
)
453 startSequence
= oldCurrentAction
!= currentAction
;
454 actions
[currentAction
].Create(at
, position
, data
, lengthData
);
456 actions
[currentAction
].Create(startAction
);
457 maxAction
= currentAction
;
460 void UndoHistory::BeginUndoAction() {
462 if (undoSequenceDepth
== 0) {
463 if (actions
[currentAction
].at
!= startAction
) {
465 actions
[currentAction
].Create(startAction
);
466 maxAction
= currentAction
;
468 actions
[currentAction
].mayCoalesce
= false;
473 void UndoHistory::EndUndoAction() {
474 PLATFORM_ASSERT(undoSequenceDepth
> 0);
477 if (0 == undoSequenceDepth
) {
478 if (actions
[currentAction
].at
!= startAction
) {
480 actions
[currentAction
].Create(startAction
);
481 maxAction
= currentAction
;
483 actions
[currentAction
].mayCoalesce
= false;
487 void UndoHistory::DropUndoSequence() {
488 undoSequenceDepth
= 0;
491 void UndoHistory::DeleteUndoHistory() {
492 for (int i
= 1; i
< maxAction
; i
++)
493 actions
[i
].Destroy();
496 actions
[currentAction
].Create(startAction
);
500 void UndoHistory::SetSavePoint() {
501 savePoint
= currentAction
;
504 bool UndoHistory::IsSavePoint() const {
505 return savePoint
== currentAction
;
508 bool UndoHistory::CanUndo() const {
509 return (currentAction
> 0) && (maxAction
> 0);
512 int UndoHistory::StartUndo() {
513 // Drop any trailing startAction
514 if (actions
[currentAction
].at
== startAction
&& currentAction
> 0)
517 // Count the steps in this action
518 int act
= currentAction
;
519 while (actions
[act
].at
!= startAction
&& act
> 0) {
522 return currentAction
- act
;
525 const Action
&UndoHistory::GetUndoStep() const {
526 return actions
[currentAction
];
529 void UndoHistory::CompletedUndoStep() {
533 bool UndoHistory::CanRedo() const {
534 return maxAction
> currentAction
;
537 int UndoHistory::StartRedo() {
538 // Drop any leading startAction
539 if (actions
[currentAction
].at
== startAction
&& currentAction
< maxAction
)
542 // Count the steps in this action
543 int act
= currentAction
;
544 while (actions
[act
].at
!= startAction
&& act
< maxAction
) {
547 return act
- currentAction
;
550 const Action
&UndoHistory::GetRedoStep() const {
551 return actions
[currentAction
];
554 void UndoHistory::CompletedRedoStep() {
558 CellBuffer::CellBuffer() {
560 collectingUndo
= true;
563 CellBuffer::~CellBuffer() {
566 char CellBuffer::CharAt(int position
) const {
567 return substance
.ValueAt(position
);
570 void CellBuffer::GetCharRange(char *buffer
, int position
, int lengthRetrieve
) {
571 if (lengthRetrieve
< 0)
575 if ((position
+ lengthRetrieve
) > substance
.Length()) {
576 Platform::DebugPrintf("Bad GetCharRange %d for %d of %d\n", position
,
577 lengthRetrieve
, substance
.Length());
581 for (int i
=0; i
<lengthRetrieve
; i
++) {
582 *buffer
++ = substance
.ValueAt(position
+ i
);
586 char CellBuffer::StyleAt(int position
) {
587 return style
.ValueAt(position
);
590 const char *CellBuffer::BufferPointer() {
591 return substance
.BufferPointer();
594 // The char* returned is to an allocation owned by the undo history
595 const char *CellBuffer::InsertString(int position
, const char *s
, int insertLength
, bool &startSequence
) {
597 // InsertString and DeleteChars are the bottleneck though which all changes occur
599 if (collectingUndo
) {
600 // Save into the undo/redo stack, but only the characters - not the formatting
601 // This takes up about half load time
602 data
= new char[insertLength
];
603 for (int i
= 0; i
< insertLength
; i
++) {
606 uh
.AppendAction(insertAction
, position
, data
, insertLength
, startSequence
);
609 BasicInsertString(position
, s
, insertLength
);
614 bool CellBuffer::SetStyleAt(int position
, char styleValue
, char mask
) {
616 char curVal
= style
.ValueAt(position
);
617 if ((curVal
& mask
) != styleValue
) {
618 style
.SetValueAt(position
, static_cast<char>((curVal
& ~mask
) | styleValue
));
625 bool CellBuffer::SetStyleFor(int position
, int lengthStyle
, char styleValue
, char mask
) {
626 bool changed
= false;
627 PLATFORM_ASSERT(lengthStyle
== 0 ||
628 (lengthStyle
> 0 && lengthStyle
+ position
<= style
.Length()));
629 while (lengthStyle
--) {
630 char curVal
= style
.ValueAt(position
);
631 if ((curVal
& mask
) != styleValue
) {
632 style
.SetValueAt(position
, static_cast<char>((curVal
& ~mask
) | styleValue
));
640 // The char* returned is to an allocation owned by the undo history
641 const char *CellBuffer::DeleteChars(int position
, int deleteLength
, bool &startSequence
) {
642 // InsertString and DeleteChars are the bottleneck though which all changes occur
643 PLATFORM_ASSERT(deleteLength
> 0);
646 if (collectingUndo
) {
647 // Save into the undo/redo stack, but only the characters - not the formatting
648 data
= new char[deleteLength
];
649 for (int i
= 0; i
< deleteLength
; i
++) {
650 data
[i
] = substance
.ValueAt(position
+ i
);
652 uh
.AppendAction(removeAction
, position
, data
, deleteLength
, startSequence
);
655 BasicDeleteChars(position
, deleteLength
);
660 int CellBuffer::Length() const {
661 return substance
.Length();
664 void CellBuffer::Allocate(int newSize
) {
665 substance
.ReAllocate(newSize
);
666 style
.ReAllocate(newSize
);
669 int CellBuffer::Lines() const {
673 int CellBuffer::LineStart(int line
) const {
676 else if (line
>= Lines())
679 return lv
.LineStart(line
);
682 bool CellBuffer::IsReadOnly() {
686 void CellBuffer::SetReadOnly(bool set
) {
690 void CellBuffer::SetSavePoint() {
694 bool CellBuffer::IsSavePoint() {
695 return uh
.IsSavePoint();
698 int CellBuffer::AddMark(int line
, int markerNum
) {
699 if ((line
>= 0) && (line
< Lines())) {
700 return lv
.AddMark(line
, markerNum
);
705 void CellBuffer::DeleteMark(int line
, int markerNum
) {
706 if ((line
>= 0) && (line
< Lines())) {
707 lv
.DeleteMark(line
, markerNum
, false);
711 void CellBuffer::DeleteMarkFromHandle(int markerHandle
) {
712 lv
.DeleteMarkFromHandle(markerHandle
);
715 int CellBuffer::GetMark(int line
) {
716 if ((line
>= 0) && (line
< Lines()))
717 return lv
.MarkValue(line
);
721 void CellBuffer::DeleteAllMarks(int markerNum
) {
722 for (int line
= 0; line
< Lines(); line
++) {
723 lv
.DeleteMark(line
, markerNum
, true);
727 int CellBuffer::LineFromHandle(int markerHandle
) {
728 return lv
.LineFromHandle(markerHandle
);
733 void CellBuffer::InsertLine(int line
, int position
) {
734 lv
.InsertLine(line
, position
);
735 if (lineStates
.Length()) {
736 lineStates
.EnsureLength(line
);
737 lineStates
.Insert(line
, 0);
741 void CellBuffer::RemoveLine(int line
) {
743 if (lineStates
.Length() > line
) {
744 lineStates
.Delete(line
);
748 void CellBuffer::BasicInsertString(int position
, const char *s
, int insertLength
) {
749 if (insertLength
== 0)
751 PLATFORM_ASSERT(insertLength
> 0);
753 substance
.InsertFromArray(position
, s
, 0, insertLength
);
754 style
.InsertValue(position
, insertLength
, 0);
756 int lineInsert
= lv
.LineFromPosition(position
) + 1;
757 // Point all the lines after the insertion point further along in the buffer
758 lv
.InsertText(lineInsert
-1, insertLength
);
759 char chPrev
= substance
.ValueAt(position
- 1);
760 char chAfter
= substance
.ValueAt(position
+ insertLength
);
761 if (chPrev
== '\r' && chAfter
== '\n') {
762 // Splitting up a crlf pair at position
763 InsertLine(lineInsert
, position
);
767 for (int i
= 0; i
< insertLength
; i
++) {
770 InsertLine(lineInsert
, (position
+ i
) + 1);
772 } else if (ch
== '\n') {
773 if (chPrev
== '\r') {
774 // Patch up what was end of line
775 lv
.SetLineStart(lineInsert
- 1, (position
+ i
) + 1);
777 InsertLine(lineInsert
, (position
+ i
) + 1);
783 // Joining two lines where last insertion is cr and following substance starts with lf
784 if (chAfter
== '\n') {
786 // End of line already in buffer so drop the newly created one
787 RemoveLine(lineInsert
- 1);
792 void CellBuffer::BasicDeleteChars(int position
, int deleteLength
) {
793 if (deleteLength
== 0)
796 if ((position
== 0) && (deleteLength
== substance
.Length())) {
797 // If whole buffer is being deleted, faster to reinitialise lines data
798 // than to delete each line.
801 // Have to fix up line positions before doing deletion as looking at text in buffer
802 // to work out which lines have been removed
804 int lineRemove
= lv
.LineFromPosition(position
) + 1;
805 lv
.InsertText(lineRemove
-1, - (deleteLength
));
806 char chPrev
= substance
.ValueAt(position
- 1);
807 char chBefore
= chPrev
;
808 char chNext
= substance
.ValueAt(position
);
809 bool ignoreNL
= false;
810 if (chPrev
== '\r' && chNext
== '\n') {
812 lv
.SetLineStart(lineRemove
, position
);
814 ignoreNL
= true; // First \n is not real deletion
818 for (int i
= 0; i
< deleteLength
; i
++) {
819 chNext
= substance
.ValueAt(position
+ i
+ 1);
821 if (chNext
!= '\n') {
822 RemoveLine(lineRemove
);
824 } else if (ch
== '\n') {
826 ignoreNL
= false; // Further \n are real deletions
828 RemoveLine(lineRemove
);
834 // May have to fix up end if last deletion causes cr to be next to lf
835 // or removes one of a crlf pair
836 char chAfter
= substance
.ValueAt(position
+ deleteLength
);
837 if (chBefore
== '\r' && chAfter
== '\n') {
838 // Using lineRemove-1 as cr ended line before start of deletion
839 RemoveLine(lineRemove
- 1);
840 lv
.SetLineStart(lineRemove
- 1, position
+ 1);
843 substance
.DeleteRange(position
, deleteLength
);
844 style
.DeleteRange(position
, deleteLength
);
847 bool CellBuffer::SetUndoCollection(bool collectUndo
) {
848 collectingUndo
= collectUndo
;
849 uh
.DropUndoSequence();
850 return collectingUndo
;
853 bool CellBuffer::IsCollectingUndo() {
854 return collectingUndo
;
857 void CellBuffer::BeginUndoAction() {
858 uh
.BeginUndoAction();
861 void CellBuffer::EndUndoAction() {
865 void CellBuffer::DeleteUndoHistory() {
866 uh
.DeleteUndoHistory();
869 bool CellBuffer::CanUndo() {
873 int CellBuffer::StartUndo() {
874 return uh
.StartUndo();
877 const Action
&CellBuffer::GetUndoStep() const {
878 return uh
.GetUndoStep();
881 void CellBuffer::PerformUndoStep() {
882 const Action
&actionStep
= uh
.GetUndoStep();
883 if (actionStep
.at
== insertAction
) {
884 BasicDeleteChars(actionStep
.position
, actionStep
.lenData
);
885 } else if (actionStep
.at
== removeAction
) {
886 BasicInsertString(actionStep
.position
, actionStep
.data
, actionStep
.lenData
);
888 uh
.CompletedUndoStep();
891 bool CellBuffer::CanRedo() {
895 int CellBuffer::StartRedo() {
896 return uh
.StartRedo();
899 const Action
&CellBuffer::GetRedoStep() const {
900 return uh
.GetRedoStep();
903 void CellBuffer::PerformRedoStep() {
904 const Action
&actionStep
= uh
.GetRedoStep();
905 if (actionStep
.at
== insertAction
) {
906 BasicInsertString(actionStep
.position
, actionStep
.data
, actionStep
.lenData
);
907 } else if (actionStep
.at
== removeAction
) {
908 BasicDeleteChars(actionStep
.position
, actionStep
.lenData
);
910 uh
.CompletedRedoStep();
913 int CellBuffer::SetLineState(int line
, int state
) {
914 lineStates
.EnsureLength(line
+ 1);
915 int stateOld
= lineStates
[line
];
916 lineStates
[line
] = state
;
920 int CellBuffer::GetLineState(int line
) {
921 lineStates
.EnsureLength(line
+ 1);
922 return lineStates
[line
];
925 int CellBuffer::GetMaxLineState() {
926 return lineStates
.Length();
929 int CellBuffer::SetLevel(int line
, int level
) {
930 return lv
.SetLevel(line
, level
);
933 int CellBuffer::GetLevel(int line
) {
934 return lv
.GetLevel(line
);
937 void CellBuffer::ClearLevels() {