2 * Copyright (c) 2017 The xterm.js authors. All rights reserved.
6 import { CircularList, IInsertEvent } from 'common/CircularList';
7 import { IBuffer, BufferIndex, IBufferStringIterator, IBufferStringIteratorResult } from 'common/buffer/Types';
8 import { IBufferLine, ICellData, IAttributeData, ICharset } from 'common/Types';
9 import { BufferLine, DEFAULT_ATTR_DATA } from 'common/buffer/BufferLine';
10 import { CellData } from 'common/buffer/CellData';
11 import { NULL_CELL_CHAR, NULL_CELL_WIDTH, NULL_CELL_CODE, WHITESPACE_CELL_CHAR, WHITESPACE_CELL_WIDTH, WHITESPACE_CELL_CODE, CHAR_DATA_WIDTH_INDEX, CHAR_DATA_CHAR_INDEX } from 'common/buffer/Constants';
12 import { reflowLargerApplyNewLayout, reflowLargerCreateNewLayout, reflowLargerGetLinesToRemove, reflowSmallerGetNewLineLengths, getWrappedLineTrimmedLength } from 'common/buffer/BufferReflow';
13 import { Marker } from 'common/buffer/Marker';
14 import { IOptionsService, IBufferService } from 'common/services/Services';
15 import { DEFAULT_CHARSET } from 'common/data/Charsets';
17 export const MAX_BUFFER_SIZE = 4294967295; // 2^32 - 1
20 * This class represents a terminal buffer (an internal state of the terminal), where the
21 * following information is stored (in high-level):
22 * - text content of this particular buffer
26 export class Buffer implements IBuffer {
27 public lines: CircularList<IBufferLine>;
28 public ydisp: number = 0;
29 public ybase: number = 0;
32 public scrollBottom: number;
33 public scrollTop: number;
36 public savedY: number = 0;
37 public savedX: number = 0;
38 public savedCurAttrData = DEFAULT_ATTR_DATA.clone();
39 public savedCharset: ICharset | null = DEFAULT_CHARSET;
40 public markers: Marker[] = [];
41 private _nullCell: ICellData = CellData.fromCharData([0, NULL_CELL_CHAR, NULL_CELL_WIDTH, NULL_CELL_CODE]);
42 private _whitespaceCell: ICellData = CellData.fromCharData([0, WHITESPACE_CELL_CHAR, WHITESPACE_CELL_WIDTH, WHITESPACE_CELL_CODE]);
43 private _cols: number;
44 private _rows: number;
47 private _hasScrollback: boolean,
48 private _optionsService: IOptionsService,
49 private _bufferService: IBufferService
51 this._cols = this._bufferService.cols;
52 this._rows = this._bufferService.rows;
53 this.lines = new CircularList<IBufferLine>(this._getCorrectBufferLength(this._rows));
55 this.scrollBottom = this._rows - 1;
59 public getNullCell(attr?: IAttributeData): ICellData {
61 this._nullCell.fg = attr.fg;
62 this._nullCell.bg = attr.bg;
64 this._nullCell.fg = 0;
65 this._nullCell.bg = 0;
67 return this._nullCell;
70 public getWhitespaceCell(attr?: IAttributeData): ICellData {
72 this._whitespaceCell.fg = attr.fg;
73 this._whitespaceCell.bg = attr.bg;
75 this._whitespaceCell.fg = 0;
76 this._whitespaceCell.bg = 0;
78 return this._whitespaceCell;
81 public getBlankLine(attr: IAttributeData, isWrapped?: boolean): IBufferLine {
82 return new BufferLine(this._bufferService.cols, this.getNullCell(attr), isWrapped);
85 public get hasScrollback(): boolean {
86 return this._hasScrollback && this.lines.maxLength > this._rows;
89 public get isCursorInViewport(): boolean {
90 const absoluteY = this.ybase + this.y;
91 const relativeY = absoluteY - this.ydisp;
92 return (relativeY >= 0 && relativeY < this._rows);
96 * Gets the correct buffer length based on the rows provided, the terminal's
97 * scrollback and whether this buffer is flagged to have scrollback or not.
98 * @param rows The terminal rows to use in the calculation.
100 private _getCorrectBufferLength(rows: number): number {
101 if (!this._hasScrollback) {
105 const correctBufferLength = rows + this._optionsService.options.scrollback;
107 return correctBufferLength > MAX_BUFFER_SIZE ? MAX_BUFFER_SIZE : correctBufferLength;
111 * Fills the buffer's viewport with blank lines.
113 public fillViewportRows(fillAttr?: IAttributeData): void {
114 if (this.lines.length === 0) {
115 if (fillAttr === undefined) {
116 fillAttr = DEFAULT_ATTR_DATA;
120 this.lines.push(this.getBlankLine(fillAttr));
126 * Clears the buffer to it's initial state, discarding all previous data.
128 public clear(): void {
133 this.lines = new CircularList<IBufferLine>(this._getCorrectBufferLength(this._rows));
135 this.scrollBottom = this._rows - 1;
136 this.setupTabStops();
140 * Resizes the buffer, adjusting its data accordingly.
141 * @param newCols The new number of columns.
142 * @param newRows The new number of rows.
144 public resize(newCols: number, newRows: number): void {
145 // store reference to null cell with default attrs
146 const nullCell = this.getNullCell(DEFAULT_ATTR_DATA);
148 // Increase max length if needed before adjustments to allow space to fill
150 const newMaxLength = this._getCorrectBufferLength(newRows);
151 if (newMaxLength > this.lines.maxLength) {
152 this.lines.maxLength = newMaxLength;
155 // The following adjustments should only happen if the buffer has been
156 // initialized/filled.
157 if (this.lines.length > 0) {
158 // Deal with columns increasing (reducing needs to happen after reflow)
159 if (this._cols < newCols) {
160 for (let i = 0; i < this.lines.length; i++) {
161 this.lines.get(i)!.resize(newCols, nullCell);
165 // Resize rows in both directions as needed
167 if (this._rows < newRows) {
168 for (let y = this._rows; y < newRows; y++) {
169 if (this.lines.length < newRows + this.ybase) {
170 if (this._optionsService.options.windowsMode) {
171 // Just add the new missing rows on Windows as conpty reprints the screen with it's
172 // view of the world. Once a line enters scrollback for conpty it remains there
173 this.lines.push(new BufferLine(newCols, nullCell));
175 if (this.ybase > 0 && this.lines.length <= this.ybase + this.y + addToY + 1) {
176 // There is room above the buffer and there are no empty elements below the line,
180 if (this.ydisp > 0) {
181 // Viewport is at the top of the buffer, must increase downwards
185 // Add a blank line if there is no buffer left at the top to scroll to, or if there
186 // are blank lines after the cursor
187 this.lines.push(new BufferLine(newCols, nullCell));
192 } else { // (this._rows >= newRows)
193 for (let y = this._rows; y > newRows; y--) {
194 if (this.lines.length > newRows + this.ybase) {
195 if (this.lines.length > this.ybase + this.y + 1) {
196 // The line is a blank line below the cursor, remove it
199 // The line is the cursor, scroll down
207 // Reduce max length if needed after adjustments, this is done after as it
208 // would otherwise cut data from the bottom of the buffer.
209 if (newMaxLength < this.lines.maxLength) {
210 // Trim from the top of the buffer and adjust ybase and ydisp.
211 const amountToTrim = this.lines.length - newMaxLength;
212 if (amountToTrim > 0) {
213 this.lines.trimStart(amountToTrim);
214 this.ybase = Math.max(this.ybase - amountToTrim, 0);
215 this.ydisp = Math.max(this.ydisp - amountToTrim, 0);
216 this.savedY = Math.max(this.savedY - amountToTrim, 0);
218 this.lines.maxLength = newMaxLength;
221 // Make sure that the cursor stays on screen
222 this.x = Math.min(this.x, newCols - 1);
223 this.y = Math.min(this.y, newRows - 1);
227 this.savedX = Math.min(this.savedX, newCols - 1);
232 this.scrollBottom = newRows - 1;
234 if (this._isReflowEnabled) {
235 this._reflow(newCols, newRows);
237 // Trim the end of the line off if cols shrunk
238 if (this._cols > newCols) {
239 for (let i = 0; i < this.lines.length; i++) {
240 this.lines.get(i)!.resize(newCols, nullCell);
245 this._cols = newCols;
246 this._rows = newRows;
249 private get _isReflowEnabled(): boolean {
250 return this._hasScrollback && !this._optionsService.options.windowsMode;
253 private _reflow(newCols: number, newRows: number): void {
254 if (this._cols === newCols) {
258 // Iterate through rows, ignore the last one as it cannot be wrapped
259 if (newCols > this._cols) {
260 this._reflowLarger(newCols, newRows);
262 this._reflowSmaller(newCols, newRows);
266 private _reflowLarger(newCols: number, newRows: number): void {
267 const toRemove: number[] = reflowLargerGetLinesToRemove(this.lines, this._cols, newCols, this.ybase + this.y, this.getNullCell(DEFAULT_ATTR_DATA));
268 if (toRemove.length > 0) {
269 const newLayoutResult = reflowLargerCreateNewLayout(this.lines, toRemove);
270 reflowLargerApplyNewLayout(this.lines, newLayoutResult.layout);
271 this._reflowLargerAdjustViewport(newCols, newRows, newLayoutResult.countRemoved);
275 private _reflowLargerAdjustViewport(newCols: number, newRows: number, countRemoved: number): void {
276 const nullCell = this.getNullCell(DEFAULT_ATTR_DATA);
277 // Adjust viewport based on number of items removed
278 let viewportAdjustments = countRemoved;
279 while (viewportAdjustments-- > 0) {
280 if (this.ybase === 0) {
284 if (this.lines.length < newRows) {
285 // Add an extra row at the bottom of the viewport
286 this.lines.push(new BufferLine(newCols, nullCell));
289 if (this.ydisp === this.ybase) {
295 this.savedY = Math.max(this.savedY - countRemoved, 0);
298 private _reflowSmaller(newCols: number, newRows: number): void {
299 const nullCell = this.getNullCell(DEFAULT_ATTR_DATA);
300 // Gather all BufferLines that need to be inserted into the Buffer here so that they can be
301 // batched up and only committed once
303 let countToInsert = 0;
304 // Go backwards as many lines may be trimmed and this will avoid considering them
305 for (let y = this.lines.length - 1; y >= 0; y--) {
306 // Check whether this line is a problem
307 let nextLine = this.lines.get(y) as BufferLine;
308 if (!nextLine || !nextLine.isWrapped && nextLine.getTrimmedLength() <= newCols) {
312 // Gather wrapped lines and adjust y to be the starting line
313 const wrappedLines: BufferLine[] = [nextLine];
314 while (nextLine.isWrapped && y > 0) {
315 nextLine = this.lines.get(--y) as BufferLine;
316 wrappedLines.unshift(nextLine);
319 // If these lines contain the cursor don't touch them, the program will handle fixing up
320 // wrapped lines with the cursor
321 const absoluteY = this.ybase + this.y;
322 if (absoluteY >= y && absoluteY < y + wrappedLines.length) {
326 const lastLineLength = wrappedLines[wrappedLines.length - 1].getTrimmedLength();
327 const destLineLengths = reflowSmallerGetNewLineLengths(wrappedLines, this._cols, newCols);
328 const linesToAdd = destLineLengths.length - wrappedLines.length;
329 let trimmedLines: number;
330 if (this.ybase === 0 && this.y !== this.lines.length - 1) {
331 // If the top section of the buffer is not yet filled
332 trimmedLines = Math.max(0, this.y - this.lines.maxLength + linesToAdd);
334 trimmedLines = Math.max(0, this.lines.length - this.lines.maxLength + linesToAdd);
338 const newLines: BufferLine[] = [];
339 for (let i = 0; i < linesToAdd; i++) {
340 const newLine = this.getBlankLine(DEFAULT_ATTR_DATA, true) as BufferLine;
341 newLines.push(newLine);
343 if (newLines.length > 0) {
345 // countToInsert here gets the actual index, taking into account other inserted items.
346 // using this we can iterate through the list forwards
347 start: y + wrappedLines.length + countToInsert,
350 countToInsert += newLines.length;
352 wrappedLines.push(...newLines);
354 // Copy buffer data to new locations, this needs to happen backwards to do in-place
355 let destLineIndex = destLineLengths.length - 1; // Math.floor(cellsNeeded / newCols);
356 let destCol = destLineLengths[destLineIndex]; // cellsNeeded % newCols;
359 destCol = destLineLengths[destLineIndex];
361 let srcLineIndex = wrappedLines.length - linesToAdd - 1;
362 let srcCol = lastLineLength;
363 while (srcLineIndex >= 0) {
364 const cellsToCopy = Math.min(srcCol, destCol);
365 wrappedLines[destLineIndex].copyCellsFrom(wrappedLines[srcLineIndex], srcCol - cellsToCopy, destCol - cellsToCopy, cellsToCopy, true);
366 destCol -= cellsToCopy;
369 destCol = destLineLengths[destLineIndex];
371 srcCol -= cellsToCopy;
374 const wrappedLinesIndex = Math.max(srcLineIndex, 0);
375 srcCol = getWrappedLineTrimmedLength(wrappedLines, wrappedLinesIndex, this._cols);
379 // Null out the end of the line ends if a wide character wrapped to the following line
380 for (let i = 0; i < wrappedLines.length; i++) {
381 if (destLineLengths[i] < newCols) {
382 wrappedLines[i].setCell(destLineLengths[i], nullCell);
386 // Adjust viewport as needed
387 let viewportAdjustments = linesToAdd - trimmedLines;
388 while (viewportAdjustments-- > 0) {
389 if (this.ybase === 0) {
390 if (this.y < newRows - 1) {
398 // Ensure ybase does not exceed its maximum value
399 if (this.ybase < Math.min(this.lines.maxLength, this.lines.length + countToInsert) - newRows) {
400 if (this.ybase === this.ydisp) {
407 this.savedY = Math.min(this.savedY + linesToAdd, this.ybase + newRows - 1);
410 // Rearrange lines in the buffer if there are any insertions, this is done at the end rather
411 // than earlier so that it's a single O(n) pass through the buffer, instead of O(n^2) from many
412 // costly calls to CircularList.splice.
413 if (toInsert.length > 0) {
414 // Record buffer insert events and then play them back backwards so that the indexes are
416 const insertEvents: IInsertEvent[] = [];
418 // Record original lines so they don't get overridden when we rearrange the list
419 const originalLines: BufferLine[] = [];
420 for (let i = 0; i < this.lines.length; i++) {
421 originalLines.push(this.lines.get(i) as BufferLine);
423 const originalLinesLength = this.lines.length;
425 let originalLineIndex = originalLinesLength - 1;
426 let nextToInsertIndex = 0;
427 let nextToInsert = toInsert[nextToInsertIndex];
428 this.lines.length = Math.min(this.lines.maxLength, this.lines.length + countToInsert);
429 let countInsertedSoFar = 0;
430 for (let i = Math.min(this.lines.maxLength - 1, originalLinesLength + countToInsert - 1); i >= 0; i--) {
431 if (nextToInsert && nextToInsert.start > originalLineIndex + countInsertedSoFar) {
432 // Insert extra lines here, adjusting i as needed
433 for (let nextI = nextToInsert.newLines.length - 1; nextI >= 0; nextI--) {
434 this.lines.set(i--, nextToInsert.newLines[nextI]);
438 // Create insert events for later
440 index: originalLineIndex + 1,
441 amount: nextToInsert.newLines.length
444 countInsertedSoFar += nextToInsert.newLines.length;
445 nextToInsert = toInsert[++nextToInsertIndex];
447 this.lines.set(i, originalLines[originalLineIndex--]);
452 let insertCountEmitted = 0;
453 for (let i = insertEvents.length - 1; i >= 0; i--) {
454 insertEvents[i].index += insertCountEmitted;
455 this.lines.onInsertEmitter.fire(insertEvents[i]);
456 insertCountEmitted += insertEvents[i].amount;
458 const amountToTrim = Math.max(0, originalLinesLength + countToInsert - this.lines.maxLength);
459 if (amountToTrim > 0) {
460 this.lines.onTrimEmitter.fire(amountToTrim);
465 // private _reflowSmallerGetLinesNeeded()
468 * Translates a string index back to a BufferIndex.
469 * To get the correct buffer position the string must start at `startCol` 0
470 * (default in translateBufferLineToString).
471 * The method also works on wrapped line strings given rows were not trimmed.
472 * The method operates on the CharData string length, there are no
473 * additional content or boundary checks. Therefore the string and the buffer
474 * should not be altered in between.
475 * TODO: respect trim flag after fixing #1685
476 * @param lineIndex line index the string was retrieved from
477 * @param stringIndex index within the string
478 * @param startCol column offset the string was retrieved from
480 public stringIndexToBufferIndex(lineIndex: number, stringIndex: number, trimRight: boolean = false): BufferIndex {
481 while (stringIndex) {
482 const line = this.lines.get(lineIndex);
486 const length = (trimRight) ? line.getTrimmedLength() : line.length;
487 for (let i = 0; i < length; ++i) {
488 if (line.get(i)[CHAR_DATA_WIDTH_INDEX]) {
489 // empty cells report a string length of 0, but get replaced
490 // with a whitespace in translateToString, thus replace with 1
491 stringIndex -= line.get(i)[CHAR_DATA_CHAR_INDEX].length || 1;
493 if (stringIndex < 0) {
494 return [lineIndex, i];
499 return [lineIndex, 0];
503 * Translates a buffer line to a string, with optional start and end columns.
504 * Wide characters will count as two columns in the resulting string. This
505 * function is useful for getting the actual text underneath the raw selection
507 * @param line The line being translated.
508 * @param trimRight Whether to trim whitespace to the right.
509 * @param startCol The column to start at.
510 * @param endCol The column to end at.
512 public translateBufferLineToString(lineIndex: number, trimRight: boolean, startCol: number = 0, endCol?: number): string {
513 const line = this.lines.get(lineIndex);
517 return line.translateToString(trimRight, startCol, endCol);
520 public getWrappedRangeForLine(y: number): { first: number, last: number } {
523 // Scan upwards for wrapped lines
524 while (first > 0 && this.lines.get(first)!.isWrapped) {
527 // Scan downwards for wrapped lines
528 while (last + 1 < this.lines.length && this.lines.get(last + 1)!.isWrapped) {
531 return { first, last };
535 * Setup the tab stops.
536 * @param i The index to start setting up tab stops from.
538 public setupTabStops(i?: number): void {
539 if (i !== null && i !== undefined) {
541 i = this.prevStop(i);
548 for (; i < this._cols; i += this._optionsService.options.tabStopWidth) {
554 * Move the cursor to the previous tab stop from the given position (default is current).
555 * @param x The position to move the cursor to the previous tab stop.
557 public prevStop(x?: number): number {
558 if (x === null || x === undefined) {
561 while (!this.tabs[--x] && x > 0);
562 return x >= this._cols ? this._cols - 1 : x < 0 ? 0 : x;
566 * Move the cursor one tab stop forward from the given position (default is current).
567 * @param x The position to move the cursor one tab stop forward.
569 public nextStop(x?: number): number {
570 if (x === null || x === undefined) {
573 while (!this.tabs[++x] && x < this._cols);
574 return x >= this._cols ? this._cols - 1 : x < 0 ? 0 : x;
577 public addMarker(y: number): Marker {
578 const marker = new Marker(y);
579 this.markers.push(marker);
580 marker.register(this.lines.onTrim(amount => {
581 marker.line -= amount;
582 // The marker should be disposed when the line is trimmed from the buffer
583 if (marker.line < 0) {
587 marker.register(this.lines.onInsert(event => {
588 if (marker.line >= event.index) {
589 marker.line += event.amount;
592 marker.register(this.lines.onDelete(event => {
593 // Delete the marker if it's within the range
594 if (marker.line >= event.index && marker.line < event.index + event.amount) {
598 // Shift the marker if it's after the deleted range
599 if (marker.line > event.index) {
600 marker.line -= event.amount;
603 marker.register(marker.onDispose(() => this._removeMarker(marker)));
607 private _removeMarker(marker: Marker): void {
608 this.markers.splice(this.markers.indexOf(marker), 1);
611 public iterator(trimRight: boolean, startIndex?: number, endIndex?: number, startOverscan?: number, endOverscan?: number): IBufferStringIterator {
612 return new BufferStringIterator(this, trimRight, startIndex, endIndex, startOverscan, endOverscan);
617 * Iterator to get unwrapped content strings from the buffer.
618 * The iterator returns at least the string data between the borders
619 * `startIndex` and `endIndex` (exclusive) and will expand the lines
620 * by `startOverscan` to the top and by `endOverscan` to the bottom,
621 * if no new line was found in between.
622 * It will never read/return string data beyond `startIndex - startOverscan`
623 * or `endIndex + endOverscan`. Therefore the first and last line might be truncated.
624 * It is possible to always get the full string for the first and last line as well
625 * by setting the overscan values to the actual buffer length. This not recommended
626 * since it might return the whole buffer within a single string in a worst case scenario.
628 export class BufferStringIterator implements IBufferStringIterator {
629 private _current: number;
632 private _buffer: IBuffer,
633 private _trimRight: boolean,
634 private _startIndex: number = 0,
635 private _endIndex: number = _buffer.lines.length,
636 private _startOverscan: number = 0,
637 private _endOverscan: number = 0
639 if (this._startIndex < 0) {
640 this._startIndex = 0;
642 if (this._endIndex > this._buffer.lines.length) {
643 this._endIndex = this._buffer.lines.length;
645 this._current = this._startIndex;
648 public hasNext(): boolean {
649 return this._current < this._endIndex;
652 public next(): IBufferStringIteratorResult {
653 const range = this._buffer.getWrappedRangeForLine(this._current);
654 // limit search window to overscan value at both borders
655 if (range.first < this._startIndex - this._startOverscan) {
656 range.first = this._startIndex - this._startOverscan;
658 if (range.last > this._endIndex + this._endOverscan) {
659 range.last = this._endIndex + this._endOverscan;
661 // limit to current buffer length
662 range.first = Math.max(range.first, 0);
663 range.last = Math.min(range.last, this._buffer.lines.length);
665 for (let i = range.first; i <= range.last; ++i) {
666 result += this._buffer.translateBufferLineToString(i, this._trimRight);
668 this._current = range.last + 1;
669 return {range: range, content: result};