semi-design/packages/semi-json-viewer-core/src/pieceTreeTextBuffer/pieceTreeBase.ts

/** reference from https://github.com/microsoft/vscode */

import { CharCode } from '../common/charCode';
import { Position } from '../common/position';
import { Range } from '../common/range';
import { FindMatch, ITextSnapshot, SearchData } from '../common/model';
import {
    NodeColor,
    SENTINEL,
    TreeNode,
    fixInsert,
    leftest,
    rbDelete,
    righttest,
    updateTreeMetadata,
} from './rbTreeBase';
import { Searcher, createFindMatch, isValidMatch } from '../model/textModelSearch';

// const lfRegex = new RegExp(/\r\n|\r|\n/g);
const AverageBufferSize = 65535;

function createUintArray(arr: number[]): Uint32Array | Uint16Array {
    let r;
    if (arr[arr.length - 1] < 65536) {
        r = new Uint16Array(arr.length);
    } else {
        r = new Uint32Array(arr.length);
    }
    r.set(arr, 0);
    return r;
}

class LineStarts {
    constructor(
        public readonly lineStarts: Uint32Array | Uint16Array | number[],
        public readonly cr: number,
        public readonly lf: number,
        public readonly crlf: number,
        public readonly isBasicASCII: boolean
    ) {}
}

export function createLineStartsFast(str: string, readonly: boolean = true): Uint32Array | Uint16Array | number[] {
    const r: number[] = [0];
    let rLength = 1;

    for (let i = 0, len = str.length; i < len; i++) {
        const chr = str.charCodeAt(i);

        if (chr === CharCode.CarriageReturn) {
            if (i + 1 < len && str.charCodeAt(i + 1) === CharCode.LineFeed) {
                // \r\n... case
                r[rLength++] = i + 2;
                i++; // skip \n
            } else {
                // \r... case
                r[rLength++] = i + 1;
            }
        } else if (chr === CharCode.LineFeed) {
            r[rLength++] = i + 1;
        }
    }
    if (readonly) {
        return createUintArray(r);
    } else {
        return r;
    }
}

export function createLineStarts(r: number[], str: string): LineStarts {
    r.length = 0;
    r[0] = 0;
    let rLength = 1;
    let cr = 0,
        lf = 0,
        crlf = 0;
    let isBasicASCII = true;
    for (let i = 0, len = str.length; i < len; i++) {
        const chr = str.charCodeAt(i);

        if (chr === CharCode.CarriageReturn) {
            if (i + 1 < len && str.charCodeAt(i + 1) === CharCode.LineFeed) {
                // \r\n... case
                crlf++;
                r[rLength++] = i + 2;
                i++; // skip \n
            } else {
                cr++;
                // \r... case
                r[rLength++] = i + 1;
            }
        } else if (chr === CharCode.LineFeed) {
            lf++;
            r[rLength++] = i + 1;
        } else {
            if (isBasicASCII) {
                if (chr !== CharCode.Tab && (chr < 32 || chr > 126)) {
                    isBasicASCII = false;
                }
            }
        }
    }
    const result = new LineStarts(createUintArray(r), cr, lf, crlf, isBasicASCII);
    r.length = 0;

    return result;
}

interface NodePosition {
    /**
     * Piece Index
     */
    node: TreeNode;
    /**
     * remainder in current piece.
     */
    remainder: number;
    /**
     * node start offset in document.
     */
    nodeStartOffset: number
}

export interface BufferCursor {
    /**
     * Line number in current buffer
     */
    line: number;
    /**
     * Column number in current buffer
     */
    column: number
}

export class Piece {
    readonly bufferIndex: number;
    readonly start: BufferCursor;
    readonly end: BufferCursor;
    readonly length: number;
    readonly lineFeedCnt: number;

    constructor(bufferIndex: number, start: BufferCursor, end: BufferCursor, lineFeedCnt: number, length: number) {
        this.bufferIndex = bufferIndex;
        this.start = start;
        this.end = end;
        this.lineFeedCnt = lineFeedCnt;
        this.length = length;
    }
}

export class StringBuffer {
    buffer: string;
    lineStarts: Uint32Array | Uint16Array | number[];

    constructor(buffer: string, lineStarts: Uint32Array | Uint16Array | number[]) {
        this.buffer = buffer;
        this.lineStarts = lineStarts;
    }
}

/**
 * Readonly snapshot for piece tree.
 * In a real multiple thread environment, to make snapshot reading always work correctly, we need to
 * 1. Make TreeNode.piece immutable, then reading and writing can run in parallel.
 * 2. TreeNode/Buffers normalization should not happen during snapshot reading.
 */
class PieceTreeSnapshot implements ITextSnapshot {
    private readonly _pieces: Piece[];
    private _index: number;
    private readonly _tree: PieceTreeBase;
    private readonly _BOM: string;

    constructor(tree: PieceTreeBase, BOM: string) {
        this._pieces = [];
        this._tree = tree;
        this._BOM = BOM;
        this._index = 0;
        if (tree.root !== SENTINEL) {
            tree.iterate(tree.root, node => {
                if (node !== SENTINEL) {
                    this._pieces.push(node.piece);
                }
                return true;
            });
        }
    }

    read(): string | null {
        if (this._pieces.length === 0) {
            if (this._index === 0) {
                this._index++;
                return this._BOM;
            } else {
                return null;
            }
        }

        if (this._index > this._pieces.length - 1) {
            return null;
        }

        if (this._index === 0) {
            return this._BOM + this._tree.getPieceContent(this._pieces[this._index++]);
        }
        return this._tree.getPieceContent(this._pieces[this._index++]);
    }
}

interface CacheEntry {
    node: TreeNode;
    nodeStartOffset: number;
    nodeStartLineNumber?: number
}

class PieceTreeSearchCache {
    private readonly _limit: number;
    private _cache: CacheEntry[];

    constructor(limit: number) {
        this._limit = limit;
        this._cache = [];
    }

    public get(offset: number): CacheEntry | null {
        for (let i = this._cache.length - 1; i >= 0; i--) {
            const nodePos = this._cache[i];
            if (nodePos.nodeStartOffset <= offset && nodePos.nodeStartOffset + nodePos.node.piece.length >= offset) {
                return nodePos;
            }
        }
        return null;
    }

    public get2(
        lineNumber: number
    ): {
            node: TreeNode;
            nodeStartOffset: number;
            nodeStartLineNumber: number
        } | null {
        for (let i = this._cache.length - 1; i >= 0; i--) {
            const nodePos = this._cache[i];
            if (
                nodePos.nodeStartLineNumber &&
                nodePos.nodeStartLineNumber < lineNumber &&
                nodePos.nodeStartLineNumber + nodePos.node.piece.lineFeedCnt >= lineNumber
            ) {
                return <
                    {
                        node: TreeNode;
                        nodeStartOffset: number;
                        nodeStartLineNumber: number
                    }
                >nodePos;
            }
        }
        return null;
    }

    public set(nodePosition: CacheEntry) {
        if (this._cache.length >= this._limit) {
            this._cache.shift();
        }
        this._cache.push(nodePosition);
    }

    public validate(offset: number) {
        let hasInvalidVal = false;
        const tmp: Array<CacheEntry | null> = this._cache;
        for (let i = 0; i < tmp.length; i++) {
            const nodePos = tmp[i]!;
            if (nodePos.node.parent === null || nodePos.nodeStartOffset >= offset) {
                tmp[i] = null;
                hasInvalidVal = true;
                continue;
            }
        }

        if (hasInvalidVal) {
            const newArr: CacheEntry[] = [];
            for (const entry of tmp) {
                if (entry !== null) {
                    newArr.push(entry);
                }
            }

            this._cache = newArr;
        }
    }
}

export class PieceTreeBase {
    root!: TreeNode;
    protected _buffers!: StringBuffer[]; // 0 is change buffer, others are readonly original buffer.
    protected _lineCnt!: number;
    protected _length!: number;
    protected _EOL!: '\r\n' | '\n';
    protected _EOLLength!: number;
    protected _EOLNormalized!: boolean;
    private _lastChangeBufferPos!: BufferCursor;
    private _searchCache!: PieceTreeSearchCache;
    private _lastVisitedLine!: { lineNumber: number; value: string };

    constructor(chunks: StringBuffer[], eol: '\r\n' | '\n', eolNormalized: boolean) {
        this.create(chunks, eol, eolNormalized);
    }

    create(chunks: StringBuffer[], eol: '\r\n' | '\n', eolNormalized: boolean) {
        this._buffers = [new StringBuffer('', [0])];
        this._lastChangeBufferPos = { line: 0, column: 0 };
        this.root = SENTINEL;
        this._lineCnt = 1;
        this._length = 0;
        this._EOL = eol;
        this._EOLLength = eol.length;
        this._EOLNormalized = eolNormalized;

        let lastNode: TreeNode | null = null;
        for (let i = 0, len = chunks.length; i < len; i++) {
            if (chunks[i].buffer.length > 0) {
                if (!chunks[i].lineStarts) {
                    chunks[i].lineStarts = createLineStartsFast(chunks[i].buffer);
                }

                const piece = new Piece(
                    i + 1,
                    { line: 0, column: 0 },
                    {
                        line: chunks[i].lineStarts.length - 1,
                        column: chunks[i].buffer.length - chunks[i].lineStarts[chunks[i].lineStarts.length - 1],
                    },
                    chunks[i].lineStarts.length - 1,
                    chunks[i].buffer.length
                );
                this._buffers.push(chunks[i]);
                lastNode = this.rbInsertRight(lastNode, piece);
            }
        }

        this._searchCache = new PieceTreeSearchCache(1);
        this._lastVisitedLine = { lineNumber: 0, value: '' };
        this.computeBufferMetadata();
    }

    normalizeEOL(eol: '\r\n' | '\n') {
        const averageBufferSize = AverageBufferSize;
        const min = averageBufferSize - Math.floor(averageBufferSize / 3);
        const max = min * 2;

        let tempChunk = '';
        let tempChunkLen = 0;
        const chunks: StringBuffer[] = [];

        this.iterate(this.root, node => {
            const str = this.getNodeContent(node);
            const len = str.length;
            if (tempChunkLen <= min || tempChunkLen + len < max) {
                tempChunk += str;
                tempChunkLen += len;
                return true;
            }

            // flush anyways
            const text = tempChunk.replace(/\r\n|\r|\n/g, eol);
            chunks.push(new StringBuffer(text, createLineStartsFast(text)));
            tempChunk = str;
            tempChunkLen = len;
            return true;
        });

        if (tempChunkLen > 0) {
            const text = tempChunk.replace(/\r\n|\r|\n/g, eol);
            chunks.push(new StringBuffer(text, createLineStartsFast(text)));
        }

        this.create(chunks, eol, true);
    }

    // #region Buffer API
    public getEOL(): '\r\n' | '\n' {
        return this._EOL;
    }

    public setEOL(newEOL: '\r\n' | '\n'): void {
        this._EOL = newEOL;
        this._EOLLength = this._EOL.length;
        this.normalizeEOL(newEOL);
    }

    public createSnapshot(BOM: string): ITextSnapshot {
        return new PieceTreeSnapshot(this, BOM);
    }

    public equal(other: PieceTreeBase): boolean {
        if (this.getLength() !== other.getLength()) {
            return false;
        }
        if (this.getLineCount() !== other.getLineCount()) {
            return false;
        }

        let offset = 0;
        const ret = this.iterate(this.root, node => {
            if (node === SENTINEL) {
                return true;
            }
            const str = this.getNodeContent(node);
            const len = str.length;
            const startPosition = other.nodeAt(offset);
            const endPosition = other.nodeAt(offset + len);
            const val = other.getValueInRange2(startPosition, endPosition);

            offset += len;
            return str === val;
        });

        return ret;
    }

    public getOffsetAt(lineNumber: number, column: number): number {
        let leftLen = 0; // inorder

        let x = this.root;

        while (x !== SENTINEL) {
            if (x.left !== SENTINEL && x.lf_left + 1 >= lineNumber) {
                x = x.left;
            } else if (x.lf_left + x.piece.lineFeedCnt + 1 >= lineNumber) {
                leftLen += x.size_left;
                // lineNumber >= 2
                const accumualtedValInCurrentIndex = this.getAccumulatedValue(x, lineNumber - x.lf_left - 2);
                return (leftLen += accumualtedValInCurrentIndex + column - 1);
            } else {
                lineNumber -= x.lf_left + x.piece.lineFeedCnt;
                leftLen += x.size_left + x.piece.length;
                x = x.right;
            }
        }

        return leftLen;
    }

    public getPositionAt(offset: number): Position {
        offset = Math.floor(offset);
        offset = Math.max(0, offset);

        let x = this.root;
        let lfCnt = 0;
        const originalOffset = offset;

        while (x !== SENTINEL) {
            if (x.size_left !== 0 && x.size_left >= offset) {
                x = x.left;
            } else if (x.size_left + x.piece.length >= offset) {
                const out = this.getIndexOf(x, offset - x.size_left);

                lfCnt += x.lf_left + out.index;

                if (out.index === 0) {
                    const lineStartOffset = this.getOffsetAt(lfCnt + 1, 1);
                    const column = originalOffset - lineStartOffset;
                    return new Position(lfCnt + 1, column + 1);
                }

                return new Position(lfCnt + 1, out.remainder + 1);
            } else {
                offset -= x.size_left + x.piece.length;
                lfCnt += x.lf_left + x.piece.lineFeedCnt;

                if (x.right === SENTINEL) {
                    // last node
                    const lineStartOffset = this.getOffsetAt(lfCnt + 1, 1);
                    const column = originalOffset - offset - lineStartOffset;
                    return new Position(lfCnt + 1, column + 1);
                } else {
                    x = x.right;
                }
            }
        }

        return new Position(1, 1);
    }

    public getValueInRange(range: Range, eol?: string): string {
        if (range.startLineNumber === range.endLineNumber && range.startColumn === range.endColumn) {
            return '';
        }

        const startPosition = this.nodeAt2(range.startLineNumber, range.startColumn);
        const endPosition = this.nodeAt2(range.endLineNumber, range.endColumn);

        const value = this.getValueInRange2(startPosition, endPosition);
        if (eol) {
            if (eol !== this._EOL || !this._EOLNormalized) {
                return value.replace(/\r\n|\r|\n/g, eol);
            }

            if (eol === this.getEOL() && this._EOLNormalized) {
                // if (eol === '\r\n') {}
                return value;
            }
            return value.replace(/\r\n|\r|\n/g, eol);
        }
        return value;
    }

    public getValueInRange2(startPosition: NodePosition | null, endPosition: NodePosition | null): string {
        if (!startPosition || !endPosition) {
            return "";
        }
        if (startPosition.node === endPosition.node) {
            const node = startPosition.node;
            const buffer = this._buffers[node.piece.bufferIndex].buffer;
            const startOffset = this.offsetInBuffer(node.piece.bufferIndex, node.piece.start);
            return buffer.substring(startOffset + startPosition.remainder, startOffset + endPosition.remainder);
        }

        let x = startPosition.node;
        const buffer = this._buffers[x.piece.bufferIndex].buffer;
        const startOffset = this.offsetInBuffer(x.piece.bufferIndex, x.piece.start);
        let ret = buffer.substring(startOffset + startPosition.remainder, startOffset + x.piece.length);

        x = x.next();
        while (x !== SENTINEL) {
            const buffer = this._buffers[x.piece.bufferIndex].buffer;
            const startOffset = this.offsetInBuffer(x.piece.bufferIndex, x.piece.start);

            if (x === endPosition.node) {
                ret += buffer.substring(startOffset, startOffset + endPosition.remainder);
                break;
            } else {
                ret += buffer.substr(startOffset, x.piece.length);
            }

            x = x.next();
        }

        return ret;
    }

    public getLinesContent(): string[] {
        const lines: string[] = [];
        let linesLength = 0;
        let currentLine = '';
        let danglingCR = false;

        this.iterate(this.root, node => {
            if (node === SENTINEL) {
                return true;
            }

            const piece = node.piece;
            let pieceLength = piece.length;
            if (pieceLength === 0) {
                return true;
            }

            const buffer = this._buffers[piece.bufferIndex].buffer;
            const lineStarts = this._buffers[piece.bufferIndex].lineStarts;

            const pieceStartLine = piece.start.line;
            const pieceEndLine = piece.end.line;
            let pieceStartOffset = lineStarts[pieceStartLine] + piece.start.column;

            if (danglingCR) {
                if (buffer.charCodeAt(pieceStartOffset) === CharCode.LineFeed) {
                    // pretend the \n was in the previous piece..
                    pieceStartOffset++;
                    pieceLength--;
                }
                lines[linesLength++] = currentLine;
                currentLine = '';
                danglingCR = false;
                if (pieceLength === 0) {
                    return true;
                }
            }

            if (pieceStartLine === pieceEndLine) {
                // this piece has no new lines
                if (
                    !this._EOLNormalized &&
                    buffer.charCodeAt(pieceStartOffset + pieceLength - 1) === CharCode.CarriageReturn
                ) {
                    danglingCR = true;
                    currentLine += buffer.substr(pieceStartOffset, pieceLength - 1);
                } else {
                    currentLine += buffer.substr(pieceStartOffset, pieceLength);
                }
                return true;
            }

            // add the text before the first line start in this piece
            currentLine += this._EOLNormalized
                ? buffer.substring(
                    pieceStartOffset,
                    Math.max(pieceStartOffset, lineStarts[pieceStartLine + 1] - this._EOLLength)
                )
                : buffer.substring(pieceStartOffset, lineStarts[pieceStartLine + 1]).replace(/(\r\n|\r|\n)$/, '');
            lines[linesLength++] = currentLine;

            for (let line = pieceStartLine + 1; line < pieceEndLine; line++) {
                currentLine = this._EOLNormalized
                    ? buffer.substring(lineStarts[line], lineStarts[line + 1] - this._EOLLength)
                    : buffer.substring(lineStarts[line], lineStarts[line + 1]).replace(/(\r\n|\r|\n)$/, '');
                lines[linesLength++] = currentLine;
            }

            if (
                !this._EOLNormalized &&
                buffer.charCodeAt(lineStarts[pieceEndLine] + piece.end.column - 1) === CharCode.CarriageReturn
            ) {
                danglingCR = true;
                if (piece.end.column === 0) {
                    // The last line ended with a \r, let's undo the push, it will be pushed by next iteration
                    linesLength--;
                } else {
                    currentLine = buffer.substr(lineStarts[pieceEndLine], piece.end.column - 1);
                }
            } else {
                currentLine = buffer.substr(lineStarts[pieceEndLine], piece.end.column);
            }

            return true;
        });

        if (danglingCR) {
            lines[linesLength++] = currentLine;
            currentLine = '';
        }

        lines[linesLength++] = currentLine;
        return lines;
    }

    public getLength(): number {
        return this._length;
    }

    public getLineCount(): number {
        return this._lineCnt;
    }

    public getLineContent(lineNumber: number): string {
        if (this._lastVisitedLine.lineNumber === lineNumber) {
            return this._lastVisitedLine.value;
        }

        this._lastVisitedLine.lineNumber = lineNumber;

        if (lineNumber === this._lineCnt) {
            this._lastVisitedLine.value = this.getLineRawContent(lineNumber);
        } else if (this._EOLNormalized) {
            this._lastVisitedLine.value = this.getLineRawContent(lineNumber, this._EOLLength);
        } else {
            this._lastVisitedLine.value = this.getLineRawContent(lineNumber).replace(/(\r\n|\r|\n)$/, '');
        }

        return this._lastVisitedLine.value;
    }

    private _getCharCode(nodePos: NodePosition): number {
        if (nodePos.remainder === nodePos.node.piece.length) {
            // the char we want to fetch is at the head of next node.
            const matchingNode = nodePos.node.next();
            if (!matchingNode) {
                return 0;
            }

            const buffer = this._buffers[matchingNode.piece.bufferIndex];
            const startOffset = this.offsetInBuffer(matchingNode.piece.bufferIndex, matchingNode.piece.start);
            return buffer.buffer.charCodeAt(startOffset);
        } else {
            const buffer = this._buffers[nodePos.node.piece.bufferIndex];
            const startOffset = this.offsetInBuffer(nodePos.node.piece.bufferIndex, nodePos.node.piece.start);
            const targetOffset = startOffset + nodePos.remainder;

            return buffer.buffer.charCodeAt(targetOffset);
        }
    }

    public getLineCharCode(lineNumber: number, index: number): number {
        const nodePos = this.nodeAt2(lineNumber, index + 1);
        return this._getCharCode(nodePos);
    }

    public getLineLength(lineNumber: number): number {
        if (lineNumber === this.getLineCount()) {
            const startOffset = this.getOffsetAt(lineNumber, 1);
            return this.getLength() - startOffset;
        }
        return this.getOffsetAt(lineNumber + 1, 1) - this.getOffsetAt(lineNumber, 1) - this._EOLLength;
    }

    public getCharCode(offset: number): number {
        const nodePos = this.nodeAt(offset);
        return this._getCharCode(nodePos);
    }

    public getNearestChunk(offset: number): string {
        const nodePos = this.nodeAt(offset);
        if (nodePos.remainder === nodePos.node.piece.length) {
            // the offset is at the head of next node.
            const matchingNode = nodePos.node.next();
            if (!matchingNode || matchingNode === SENTINEL) {
                return '';
            }

            const buffer = this._buffers[matchingNode.piece.bufferIndex];
            const startOffset = this.offsetInBuffer(matchingNode.piece.bufferIndex, matchingNode.piece.start);
            return buffer.buffer.substring(startOffset, startOffset + matchingNode.piece.length);
        } else {
            const buffer = this._buffers[nodePos.node.piece.bufferIndex];
            const startOffset = this.offsetInBuffer(nodePos.node.piece.bufferIndex, nodePos.node.piece.start);
            const targetOffset = startOffset + nodePos.remainder;
            const targetEnd = startOffset + nodePos.node.piece.length;
            return buffer.buffer.substring(targetOffset, targetEnd);
        }
    }

    public findMatchesInNode(
        node: TreeNode,
        searcher: Searcher,
        startLineNumber: number,
        startColumn: number,
        startCursor: BufferCursor,
        endCursor: BufferCursor,
        searchData: SearchData,
        captureMatches: boolean,
        limitResultCount: number,
        resultLen: number,
        result: FindMatch[]
    ) {
        const buffer = this._buffers[node.piece.bufferIndex];
        const startOffsetInBuffer = this.offsetInBuffer(node.piece.bufferIndex, node.piece.start);
        const start = this.offsetInBuffer(node.piece.bufferIndex, startCursor);
        const end = this.offsetInBuffer(node.piece.bufferIndex, endCursor);

        let m: RegExpExecArray | null;
        // Reset regex to search from the beginning
        const ret: BufferCursor = { line: 0, column: 0 };
        let searchText: string;
        let offsetInBuffer: (offset: number) => number;

        if (searcher._wordSeparators) {
            searchText = buffer.buffer.substring(start, end);
            offsetInBuffer = (offset: number) => offset + start;
            searcher.reset(0);
        } else {
            searchText = buffer.buffer;
            offsetInBuffer = (offset: number) => offset;
            searcher.reset(start);
        }

        do {
            m = searcher.next(searchText);

            if (m) {
                if (offsetInBuffer(m.index) >= end) {
                    return resultLen;
                }
                this.positionInBuffer(node, offsetInBuffer(m.index) - startOffsetInBuffer, ret);
                const lineFeedCnt = this.getLineFeedCnt(node.piece.bufferIndex, startCursor, ret);
                const retStartColumn =
                    ret.line === startCursor.line ? ret.column - startCursor.column + startColumn : ret.column + 1;
                const retEndColumn = retStartColumn + m[0].length;
                result[resultLen++] = createFindMatch(
                    new Range(
                        startLineNumber + lineFeedCnt,
                        retStartColumn,
                        startLineNumber + lineFeedCnt,
                        retEndColumn
                    ),
                    m,
                    captureMatches
                );

                if (offsetInBuffer(m.index) + m[0].length >= end) {
                    return resultLen;
                }
                if (resultLen >= limitResultCount) {
                    return resultLen;
                }
            }
        } while (m);

        return resultLen;
    }

    public findMatchesLineByLine(
        searchRange: Range,
        searchData: SearchData,
        captureMatches: boolean,
        limitResultCount: number
    ): FindMatch[] {
        const result: FindMatch[] = [];
        let resultLen = 0;
        const searcher = new Searcher(searchData.wordSeparators, searchData.regex);

        let startPosition = this.nodeAt2(searchRange.startLineNumber, searchRange.startColumn);
        if (startPosition === null) {
            return [];
        }
        const endPosition = this.nodeAt2(searchRange.endLineNumber, searchRange.endColumn);
        if (endPosition === null) {
            return [];
        }
        let start = this.positionInBuffer(startPosition.node, startPosition.remainder);
        const end = this.positionInBuffer(endPosition.node, endPosition.remainder);

        if (startPosition.node === endPosition.node) {
            this.findMatchesInNode(
                startPosition.node,
                searcher,
                searchRange.startLineNumber,
                searchRange.startColumn,
                start,
                end,
                searchData,
                captureMatches,
                limitResultCount,
                resultLen,
                result
            );
            return result;
        }

        let startLineNumber = searchRange.startLineNumber;

        let currentNode = startPosition.node;
        while (currentNode !== endPosition.node) {
            const lineBreakCnt = this.getLineFeedCnt(currentNode.piece.bufferIndex, start, currentNode.piece.end);

            if (lineBreakCnt >= 1) {
                // last line break position
                const lineStarts = this._buffers[currentNode.piece.bufferIndex].lineStarts;
                const startOffsetInBuffer = this.offsetInBuffer(currentNode.piece.bufferIndex, currentNode.piece.start);
                const nextLineStartOffset = lineStarts[start.line + lineBreakCnt];
                const startColumn = startLineNumber === searchRange.startLineNumber ? searchRange.startColumn : 1;
                resultLen = this.findMatchesInNode(
                    currentNode,
                    searcher,
                    startLineNumber,
                    startColumn,
                    start,
                    this.positionInBuffer(currentNode, nextLineStartOffset - startOffsetInBuffer),
                    searchData,
                    captureMatches,
                    limitResultCount,
                    resultLen,
                    result
                );

                if (resultLen >= limitResultCount) {
                    return result;
                }

                startLineNumber += lineBreakCnt;
            }

            const startColumn = startLineNumber === searchRange.startLineNumber ? searchRange.startColumn - 1 : 0;
            // search for the remaining content
            if (startLineNumber === searchRange.endLineNumber) {
                const text = this.getLineContent(startLineNumber).substring(startColumn, searchRange.endColumn - 1);
                resultLen = this._findMatchesInLine(
                    searchData,
                    searcher,
                    text,
                    searchRange.endLineNumber,
                    startColumn,
                    resultLen,
                    result,
                    captureMatches,
                    limitResultCount
                );
                return result;
            }

            resultLen = this._findMatchesInLine(
                searchData,
                searcher,
                this.getLineContent(startLineNumber).substr(startColumn),
                startLineNumber,
                startColumn,
                resultLen,
                result,
                captureMatches,
                limitResultCount
            );

            if (resultLen >= limitResultCount) {
                return result;
            }

            startLineNumber++;
            startPosition = this.nodeAt2(startLineNumber, 1);
            currentNode = startPosition.node;
            start = this.positionInBuffer(startPosition.node, startPosition.remainder);
        }

        if (startLineNumber === searchRange.endLineNumber) {
            const startColumn = startLineNumber === searchRange.startLineNumber ? searchRange.startColumn - 1 : 0;
            const text = this.getLineContent(startLineNumber).substring(startColumn, searchRange.endColumn - 1);
            resultLen = this._findMatchesInLine(
                searchData,
                searcher,
                text,
                searchRange.endLineNumber,
                startColumn,
                resultLen,
                result,
                captureMatches,
                limitResultCount
            );
            return result;
        }

        const startColumn = startLineNumber === searchRange.startLineNumber ? searchRange.startColumn : 1;
        resultLen = this.findMatchesInNode(
            endPosition.node,
            searcher,
            startLineNumber,
            startColumn,
            start,
            end,
            searchData,
            captureMatches,
            limitResultCount,
            resultLen,
            result
        );
        return result;
    }

    private _findMatchesInLine(
        searchData: SearchData,
        searcher: Searcher,
        text: string,
        lineNumber: number,
        deltaOffset: number,
        resultLen: number,
        result: FindMatch[],
        captureMatches: boolean,
        limitResultCount: number
    ): number {
        const wordSeparators = searchData.wordSeparators;
        if (!captureMatches && searchData.simpleSearch) {
            const searchString = searchData.simpleSearch;
            const searchStringLen = searchString.length;
            const textLength = text.length;

            let lastMatchIndex = -searchStringLen;
            while ((lastMatchIndex = text.indexOf(searchString, lastMatchIndex + searchStringLen)) !== -1) {
                if (
                    !wordSeparators ||
                    isValidMatch(wordSeparators, text, textLength, lastMatchIndex, searchStringLen)
                ) {
                    result[resultLen++] = new FindMatch(
                        new Range(
                            lineNumber,
                            lastMatchIndex + 1 + deltaOffset,
                            lineNumber,
                            lastMatchIndex + 1 + searchStringLen + deltaOffset
                        ),
                        null
                    );
                    if (resultLen >= limitResultCount) {
                        return resultLen;
                    }
                }
            }
            return resultLen;
        }

        let m: RegExpExecArray | null;
        // Reset regex to search from the beginning
        searcher.reset(0);
        do {
            m = searcher.next(text);
            if (m) {
                result[resultLen++] = createFindMatch(
                    new Range(
                        lineNumber,
                        m.index + 1 + deltaOffset,
                        lineNumber,
                        m.index + 1 + m[0].length + deltaOffset
                    ),
                    m,
                    captureMatches
                );
                if (resultLen >= limitResultCount) {
                    return resultLen;
                }
            }
        } while (m);
        return resultLen;
    }

    // #endregion

    // #region Piece Table
    public insert(offset: number, value: string, eolNormalized: boolean = false): void {
        this._EOLNormalized = this._EOLNormalized && eolNormalized;
        this._lastVisitedLine.lineNumber = 0;
        this._lastVisitedLine.value = '';

        if (this.root !== SENTINEL) {
            const { node, remainder, nodeStartOffset } = this.nodeAt(offset);
            const piece = node.piece;
            const bufferIndex = piece.bufferIndex;
            const insertPosInBuffer = this.positionInBuffer(node, remainder);
            if (
                node.piece.bufferIndex === 0 &&
                piece.end.line === this._lastChangeBufferPos.line &&
                piece.end.column === this._lastChangeBufferPos.column &&
                nodeStartOffset + piece.length === offset &&
                value.length < AverageBufferSize
            ) {
                // changed buffer
                this.appendToNode(node, value);
                this.computeBufferMetadata();
                return;
            }

            if (nodeStartOffset === offset) {
                this.insertContentToNodeLeft(value, node);
                this._searchCache.validate(offset);
            } else if (nodeStartOffset + node.piece.length > offset) {
                // we are inserting into the middle of a node.
                const nodesToDel: TreeNode[] = [];
                let newRightPiece = new Piece(
                    piece.bufferIndex,
                    insertPosInBuffer,
                    piece.end,
                    this.getLineFeedCnt(piece.bufferIndex, insertPosInBuffer, piece.end),
                    this.offsetInBuffer(bufferIndex, piece.end) - this.offsetInBuffer(bufferIndex, insertPosInBuffer)
                );

                if (this.shouldCheckCRLF() && this.endWithCR(value)) {
                    const headOfRight = this.nodeCharCodeAt(node, remainder);

                    if (headOfRight === 10 /** \n */) {
                        const newStart: BufferCursor = {
                            line: newRightPiece.start.line + 1,
                            column: 0,
                        };
                        newRightPiece = new Piece(
                            newRightPiece.bufferIndex,
                            newStart,
                            newRightPiece.end,
                            this.getLineFeedCnt(newRightPiece.bufferIndex, newStart, newRightPiece.end),
                            newRightPiece.length - 1
                        );

                        value += '\n';
                    }
                }

                // reuse node for content before insertion point.
                if (this.shouldCheckCRLF() && this.startWithLF(value)) {
                    const tailOfLeft = this.nodeCharCodeAt(node, remainder - 1);
                    if (tailOfLeft === 13 /** \r */) {
                        const previousPos = this.positionInBuffer(node, remainder - 1);
                        this.deleteNodeTail(node, previousPos);
                        value = '\r' + value;

                        if (node.piece.length === 0) {
                            nodesToDel.push(node);
                        }
                    } else {
                        this.deleteNodeTail(node, insertPosInBuffer);
                    }
                } else {
                    this.deleteNodeTail(node, insertPosInBuffer);
                }

                const newPieces = this.createNewPieces(value);
                if (newRightPiece.length > 0) {
                    this.rbInsertRight(node, newRightPiece);
                }

                let tmpNode = node;
                for (let k = 0; k < newPieces.length; k++) {
                    tmpNode = this.rbInsertRight(tmpNode, newPieces[k]);
                }
                this.deleteNodes(nodesToDel);
            } else {
                this.insertContentToNodeRight(value, node);
            }
        } else {
            // insert new node
            const pieces = this.createNewPieces(value);
            let node = this.rbInsertLeft(null, pieces[0]);

            for (let k = 1; k < pieces.length; k++) {
                node = this.rbInsertRight(node, pieces[k]);
            }
        }

        // todo, this is too brutal. Total line feed count should be updated the same way as lf_left.
        this.computeBufferMetadata();
    }

    public delete(offset: number, cnt: number): void {
        this._lastVisitedLine.lineNumber = 0;
        this._lastVisitedLine.value = '';

        if (cnt <= 0 || this.root === SENTINEL) {
            return;
        }

        const startPosition = this.nodeAt(offset);
        const endPosition = this.nodeAt(offset + cnt);
        const startNode = startPosition.node;
        const endNode = endPosition.node;

        if (startNode === endNode) {
            const startSplitPosInBuffer = this.positionInBuffer(startNode, startPosition.remainder);
            const endSplitPosInBuffer = this.positionInBuffer(startNode, endPosition.remainder);

            if (startPosition.nodeStartOffset === offset) {
                if (cnt === startNode.piece.length) {
                    // delete node
                    const next = startNode.next();
                    rbDelete(this, startNode);
                    this.validateCRLFWithPrevNode(next);
                    this.computeBufferMetadata();
                    return;
                }
                this.deleteNodeHead(startNode, endSplitPosInBuffer);
                this._searchCache.validate(offset);
                this.validateCRLFWithPrevNode(startNode);
                this.computeBufferMetadata();
                return;
            }

            if (startPosition.nodeStartOffset + startNode.piece.length === offset + cnt) {
                this.deleteNodeTail(startNode, startSplitPosInBuffer);
                this.validateCRLFWithNextNode(startNode);
                this.computeBufferMetadata();
                return;
            }

            // delete content in the middle, this node will be splitted to nodes
            this.shrinkNode(startNode, startSplitPosInBuffer, endSplitPosInBuffer);
            this.computeBufferMetadata();
            return;
        }

        const nodesToDel: TreeNode[] = [];

        const startSplitPosInBuffer = this.positionInBuffer(startNode, startPosition.remainder);
        this.deleteNodeTail(startNode, startSplitPosInBuffer);
        this._searchCache.validate(offset);
        if (startNode.piece.length === 0) {
            nodesToDel.push(startNode);
        }

        // update last touched node
        const endSplitPosInBuffer = this.positionInBuffer(endNode, endPosition.remainder);
        this.deleteNodeHead(endNode, endSplitPosInBuffer);
        if (endNode.piece.length === 0) {
            nodesToDel.push(endNode);
        }

        // delete nodes in between
        const secondNode = startNode.next();
        for (let node = secondNode; node !== SENTINEL && node !== endNode; node = node.next()) {
            nodesToDel.push(node);
        }

        const prev = startNode.piece.length === 0 ? startNode.prev() : startNode;
        this.deleteNodes(nodesToDel);
        this.validateCRLFWithNextNode(prev);
        this.computeBufferMetadata();
    }

    private insertContentToNodeLeft(value: string, node: TreeNode) {
        // we are inserting content to the beginning of node
        const nodesToDel: TreeNode[] = [];
        if (this.shouldCheckCRLF() && this.endWithCR(value) && this.startWithLF(node)) {
            // move `\n` to new node.

            const piece = node.piece;
            const newStart: BufferCursor = { line: piece.start.line + 1, column: 0 };
            const nPiece = new Piece(
                piece.bufferIndex,
                newStart,
                piece.end,
                this.getLineFeedCnt(piece.bufferIndex, newStart, piece.end),
                piece.length - 1
            );

            node.piece = nPiece;

            value += '\n';
            updateTreeMetadata(this, node, -1, -1);

            if (node.piece.length === 0) {
                nodesToDel.push(node);
            }
        }

        const newPieces = this.createNewPieces(value);
        let newNode = this.rbInsertLeft(node, newPieces[newPieces.length - 1]);
        for (let k = newPieces.length - 2; k >= 0; k--) {
            newNode = this.rbInsertLeft(newNode, newPieces[k]);
        }
        this.validateCRLFWithPrevNode(newNode);
        this.deleteNodes(nodesToDel);
    }

    private insertContentToNodeRight(value: string, node: TreeNode) {
        // we are inserting to the right of this node.
        if (this.adjustCarriageReturnFromNext(value, node)) {
            // move \n to the new node.
            value += '\n';
        }

        const newPieces = this.createNewPieces(value);
        const newNode = this.rbInsertRight(node, newPieces[0]);
        let tmpNode = newNode;

        for (let k = 1; k < newPieces.length; k++) {
            tmpNode = this.rbInsertRight(tmpNode, newPieces[k]);
        }

        this.validateCRLFWithPrevNode(newNode);
    }

    private positionInBuffer(node: TreeNode, remainder: number): BufferCursor;
    private positionInBuffer(node: TreeNode, remainder: number, ret: BufferCursor): null;
    private positionInBuffer(node: TreeNode, remainder: number, ret?: BufferCursor): BufferCursor | null {
        const piece = node.piece;
        const bufferIndex = node.piece.bufferIndex;
        const lineStarts = this._buffers[bufferIndex].lineStarts;

        const startOffset = lineStarts[piece.start.line] + piece.start.column;

        const offset = startOffset + remainder;

        // binary search offset between startOffset and endOffset
        let low = piece.start.line;
        let high = piece.end.line;

        let mid: number = 0;
        let midStop: number = 0;
        let midStart: number = 0;

        while (low <= high) {
            mid = (low + (high - low) / 2) | 0;
            midStart = lineStarts[mid];

            if (mid === high) {
                break;
            }

            midStop = lineStarts[mid + 1];

            if (offset < midStart) {
                high = mid - 1;
            } else if (offset >= midStop) {
                low = mid + 1;
            } else {
                break;
            }
        }

        if (ret) {
            ret.line = mid;
            ret.column = offset - midStart;
            return null;
        }

        return {
            line: mid,
            column: offset - midStart,
        };
    }

    private getLineFeedCnt(bufferIndex: number, start: BufferCursor, end: BufferCursor): number {
        // we don't need to worry about start: abc\r|\n, or abc|\r, or abc|\n, or abc|\r\n doesn't change the fact that, there is one line break after start.
        // now let's take care of end: abc\r|\n, if end is in between \r and \n, we need to add line feed count by 1
        if (end.column === 0) {
            return end.line - start.line;
        }

        const lineStarts = this._buffers[bufferIndex].lineStarts;
        if (end.line === lineStarts.length - 1) {
            // it means, there is no \n after end, otherwise, there will be one more lineStart.
            return end.line - start.line;
        }

        const nextLineStartOffset = lineStarts[end.line + 1];
        const endOffset = lineStarts[end.line] + end.column;
        if (nextLineStartOffset > endOffset + 1) {
            // there are more than 1 character after end, which means it can't be \n
            return end.line - start.line;
        }
        // endOffset + 1 === nextLineStartOffset
        // character at endOffset is \n, so we check the character before first
        // if character at endOffset is \r, end.column is 0 and we can't get here.
        const previousCharOffset = endOffset - 1; // end.column > 0 so it's okay.
        const buffer = this._buffers[bufferIndex].buffer;

        if (buffer.charCodeAt(previousCharOffset) === 13) {
            return end.line - start.line + 1;
        } else {
            return end.line - start.line;
        }
    }

    private offsetInBuffer(bufferIndex: number, cursor: BufferCursor): number {
        const lineStarts = this._buffers[bufferIndex].lineStarts;
        return lineStarts[cursor.line] + cursor.column;
    }

    private deleteNodes(nodes: TreeNode[]): void {
        for (let i = 0; i < nodes.length; i++) {
            rbDelete(this, nodes[i]);
        }
    }

    private createNewPieces(text: string): Piece[] {
        if (text.length > AverageBufferSize) {
            // the content is large, operations like substring, charCode becomes slow
            // so here we split it into smaller chunks, just like what we did for CR/LF normalization
            const newPieces: Piece[] = [];
            while (text.length > AverageBufferSize) {
                const lastChar = text.charCodeAt(AverageBufferSize - 1);
                let splitText;
                if (lastChar === CharCode.CarriageReturn || (lastChar >= 0xd800 && lastChar <= 0xdbff)) {
                    // last character is \r or a high surrogate => keep it back
                    splitText = text.substring(0, AverageBufferSize - 1);
                    text = text.substring(AverageBufferSize - 1);
                } else {
                    splitText = text.substring(0, AverageBufferSize);
                    text = text.substring(AverageBufferSize);
                }

                const lineStarts = createLineStartsFast(splitText);
                newPieces.push(
                    new Piece(
                        this._buffers.length /* buffer index */,
                        { line: 0, column: 0 },
                        {
                            line: lineStarts.length - 1,
                            column: splitText.length - lineStarts[lineStarts.length - 1],
                        },
                        lineStarts.length - 1,
                        splitText.length
                    )
                );
                this._buffers.push(new StringBuffer(splitText, lineStarts));
            }

            const lineStarts = createLineStartsFast(text);
            newPieces.push(
                new Piece(
                    this._buffers.length /* buffer index */,
                    { line: 0, column: 0 },
                    {
                        line: lineStarts.length - 1,
                        column: text.length - lineStarts[lineStarts.length - 1],
                    },
                    lineStarts.length - 1,
                    text.length
                )
            );
            this._buffers.push(new StringBuffer(text, lineStarts));

            return newPieces;
        }

        let startOffset = this._buffers[0].buffer.length;
        const lineStarts = createLineStartsFast(text, false);

        let start = this._lastChangeBufferPos;
        if (
            this._buffers[0].lineStarts[this._buffers[0].lineStarts.length - 1] === startOffset &&
            startOffset !== 0 &&
            this.startWithLF(text) &&
            this.endWithCR(this._buffers[0].buffer) // todo, we can check this._lastChangeBufferPos's column as it's the last one
        ) {
            this._lastChangeBufferPos = {
                line: this._lastChangeBufferPos.line,
                column: this._lastChangeBufferPos.column + 1,
            };
            start = this._lastChangeBufferPos;

            for (let i = 0; i < lineStarts.length; i++) {
                lineStarts[i] += startOffset + 1;
            }

            this._buffers[0].lineStarts = (<number[]> this._buffers[0].lineStarts).concat(<number[]>lineStarts.slice(1));
            this._buffers[0].buffer += '_' + text;
            startOffset += 1;
        } else {
            if (startOffset !== 0) {
                for (let i = 0; i < lineStarts.length; i++) {
                    lineStarts[i] += startOffset;
                }
            }
            this._buffers[0].lineStarts = (<number[]> this._buffers[0].lineStarts).concat(<number[]>lineStarts.slice(1));
            this._buffers[0].buffer += text;
        }

        const endOffset = this._buffers[0].buffer.length;
        const endIndex = this._buffers[0].lineStarts.length - 1;
        const endColumn = endOffset - this._buffers[0].lineStarts[endIndex];
        const endPos = { line: endIndex, column: endColumn };
        const newPiece = new Piece(
            0 /** todo@peng */,
            start,
            endPos,
            this.getLineFeedCnt(0, start, endPos),
            endOffset - startOffset
        );
        this._lastChangeBufferPos = endPos;
        return [newPiece];
    }

    public getLinesRawContent(): string {
        return this.getContentOfSubTree(this.root);
    }

    public getLineRawContent(lineNumber: number, endOffset: number = 0): string {
        let x = this.root;

        let ret = '';
        const cache = this._searchCache.get2(lineNumber);
        if (cache) {
            x = cache.node;
            const prevAccumulatedValue = this.getAccumulatedValue(x, lineNumber - cache.nodeStartLineNumber - 1);
            const buffer = this._buffers[x.piece.bufferIndex].buffer;
            const startOffset = this.offsetInBuffer(x.piece.bufferIndex, x.piece.start);
            if (cache.nodeStartLineNumber + x.piece.lineFeedCnt === lineNumber) {
                ret = buffer.substring(startOffset + prevAccumulatedValue, startOffset + x.piece.length);
            } else {
                const accumulatedValue = this.getAccumulatedValue(x, lineNumber - cache.nodeStartLineNumber);
                return buffer.substring(startOffset + prevAccumulatedValue, startOffset + accumulatedValue - endOffset);
            }
        } else {
            let nodeStartOffset = 0;
            const originalLineNumber = lineNumber;
            while (x !== SENTINEL) {
                if (x.left !== SENTINEL && x.lf_left >= lineNumber - 1) {
                    x = x.left;
                } else if (x.lf_left + x.piece.lineFeedCnt > lineNumber - 1) {
                    const prevAccumulatedValue = this.getAccumulatedValue(x, lineNumber - x.lf_left - 2);
                    const accumulatedValue = this.getAccumulatedValue(x, lineNumber - x.lf_left - 1);
                    const buffer = this._buffers[x.piece.bufferIndex].buffer;
                    const startOffset = this.offsetInBuffer(x.piece.bufferIndex, x.piece.start);
                    nodeStartOffset += x.size_left;
                    this._searchCache.set({
                        node: x,
                        nodeStartOffset,
                        nodeStartLineNumber: originalLineNumber - (lineNumber - 1 - x.lf_left),
                    });

                    return buffer.substring(
                        startOffset + prevAccumulatedValue,
                        startOffset + accumulatedValue - endOffset
                    );
                } else if (x.lf_left + x.piece.lineFeedCnt === lineNumber - 1) {
                    const prevAccumulatedValue = this.getAccumulatedValue(x, lineNumber - x.lf_left - 2);
                    const buffer = this._buffers[x.piece.bufferIndex].buffer;
                    const startOffset = this.offsetInBuffer(x.piece.bufferIndex, x.piece.start);

                    ret = buffer.substring(startOffset + prevAccumulatedValue, startOffset + x.piece.length);
                    break;
                } else {
                    lineNumber -= x.lf_left + x.piece.lineFeedCnt;
                    nodeStartOffset += x.size_left + x.piece.length;
                    x = x.right;
                }
            }
        }

        // search in order, to find the node contains end column
        x = x.next();
        while (x !== SENTINEL) {
            const buffer = this._buffers[x.piece.bufferIndex].buffer;

            if (x.piece.lineFeedCnt > 0) {
                const accumulatedValue = this.getAccumulatedValue(x, 0);
                const startOffset = this.offsetInBuffer(x.piece.bufferIndex, x.piece.start);

                ret += buffer.substring(startOffset, startOffset + accumulatedValue - endOffset);
                return ret;
            } else {
                const startOffset = this.offsetInBuffer(x.piece.bufferIndex, x.piece.start);
                ret += buffer.substr(startOffset, x.piece.length);
            }

            x = x.next();
        }

        return ret;
    }

    private computeBufferMetadata() {
        let x = this.root;

        let lfCnt = 1;
        let len = 0;

        while (x !== SENTINEL) {
            lfCnt += x.lf_left + x.piece.lineFeedCnt;
            len += x.size_left + x.piece.length;
            x = x.right;
        }

        this._lineCnt = lfCnt;
        this._length = len;
        this._searchCache.validate(this._length);
    }

    // #region node operations
    private getIndexOf(node: TreeNode, accumulatedValue: number): { index: number; remainder: number } {
        const piece = node.piece;
        const pos = this.positionInBuffer(node, accumulatedValue);
        const lineCnt = pos.line - piece.start.line;

        if (
            this.offsetInBuffer(piece.bufferIndex, piece.end) - this.offsetInBuffer(piece.bufferIndex, piece.start) ===
            accumulatedValue
        ) {
            // we are checking the end of this node, so a CRLF check is necessary.
            const realLineCnt = this.getLineFeedCnt(node.piece.bufferIndex, piece.start, pos);
            if (realLineCnt !== lineCnt) {
                // aha yes, CRLF
                return { index: realLineCnt, remainder: 0 };
            }
        }

        return { index: lineCnt, remainder: pos.column };
    }

    private getAccumulatedValue(node: TreeNode, index: number) {
        if (index < 0) {
            return 0;
        }
        const piece = node.piece;
        const lineStarts = this._buffers[piece.bufferIndex].lineStarts;
        const expectedLineStartIndex = piece.start.line + index + 1;
        if (expectedLineStartIndex > piece.end.line) {
            return lineStarts[piece.end.line] + piece.end.column - lineStarts[piece.start.line] - piece.start.column;
        } else {
            return lineStarts[expectedLineStartIndex] - lineStarts[piece.start.line] - piece.start.column;
        }
    }

    private deleteNodeTail(node: TreeNode, pos: BufferCursor) {
        const piece = node.piece;
        const originalLFCnt = piece.lineFeedCnt;
        const originalEndOffset = this.offsetInBuffer(piece.bufferIndex, piece.end);

        const newEnd = pos;
        const newEndOffset = this.offsetInBuffer(piece.bufferIndex, newEnd);
        const newLineFeedCnt = this.getLineFeedCnt(piece.bufferIndex, piece.start, newEnd);

        const lf_delta = newLineFeedCnt - originalLFCnt;
        const size_delta = newEndOffset - originalEndOffset;
        const newLength = piece.length + size_delta;

        node.piece = new Piece(piece.bufferIndex, piece.start, newEnd, newLineFeedCnt, newLength);

        updateTreeMetadata(this, node, size_delta, lf_delta);
    }

    private deleteNodeHead(node: TreeNode, pos: BufferCursor) {
        const piece = node.piece;
        const originalLFCnt = piece.lineFeedCnt;
        const originalStartOffset = this.offsetInBuffer(piece.bufferIndex, piece.start);

        const newStart = pos;
        const newLineFeedCnt = this.getLineFeedCnt(piece.bufferIndex, newStart, piece.end);
        const newStartOffset = this.offsetInBuffer(piece.bufferIndex, newStart);
        const lf_delta = newLineFeedCnt - originalLFCnt;
        const size_delta = originalStartOffset - newStartOffset;
        const newLength = piece.length + size_delta;
        node.piece = new Piece(piece.bufferIndex, newStart, piece.end, newLineFeedCnt, newLength);

        updateTreeMetadata(this, node, size_delta, lf_delta);
    }

    private shrinkNode(node: TreeNode, start: BufferCursor, end: BufferCursor) {
        const piece = node.piece;
        const originalStartPos = piece.start;
        const originalEndPos = piece.end;

        // old piece, originalStartPos, start
        const oldLength = piece.length;
        const oldLFCnt = piece.lineFeedCnt;
        const newEnd = start;
        const newLineFeedCnt = this.getLineFeedCnt(piece.bufferIndex, piece.start, newEnd);
        const newLength =
            this.offsetInBuffer(piece.bufferIndex, start) - this.offsetInBuffer(piece.bufferIndex, originalStartPos);

        node.piece = new Piece(piece.bufferIndex, piece.start, newEnd, newLineFeedCnt, newLength);

        updateTreeMetadata(this, node, newLength - oldLength, newLineFeedCnt - oldLFCnt);

        // new right piece, end, originalEndPos
        const newPiece = new Piece(
            piece.bufferIndex,
            end,
            originalEndPos,
            this.getLineFeedCnt(piece.bufferIndex, end, originalEndPos),
            this.offsetInBuffer(piece.bufferIndex, originalEndPos) - this.offsetInBuffer(piece.bufferIndex, end)
        );

        const newNode = this.rbInsertRight(node, newPiece);
        this.validateCRLFWithPrevNode(newNode);
    }

    private appendToNode(node: TreeNode, value: string): void {
        if (this.adjustCarriageReturnFromNext(value, node)) {
            value += '\n';
        }

        const hitCRLF = this.shouldCheckCRLF() && this.startWithLF(value) && this.endWithCR(node);
        const startOffset = this._buffers[0].buffer.length;
        this._buffers[0].buffer += value;
        const lineStarts = createLineStartsFast(value, false);
        for (let i = 0; i < lineStarts.length; i++) {
            lineStarts[i] += startOffset;
        }
        if (hitCRLF) {
            const prevStartOffset = this._buffers[0].lineStarts[this._buffers[0].lineStarts.length - 2];
            (<number[]> this._buffers[0].lineStarts).pop();
            // _lastChangeBufferPos is already wrong
            this._lastChangeBufferPos = {
                line: this._lastChangeBufferPos.line - 1,
                column: startOffset - prevStartOffset,
            };
        }

        this._buffers[0].lineStarts = (<number[]> this._buffers[0].lineStarts).concat(<number[]>lineStarts.slice(1));
        const endIndex = this._buffers[0].lineStarts.length - 1;
        const endColumn = this._buffers[0].buffer.length - this._buffers[0].lineStarts[endIndex];
        const newEnd = { line: endIndex, column: endColumn };
        const newLength = node.piece.length + value.length;
        const oldLineFeedCnt = node.piece.lineFeedCnt;
        const newLineFeedCnt = this.getLineFeedCnt(0, node.piece.start, newEnd);
        const lf_delta = newLineFeedCnt - oldLineFeedCnt;

        node.piece = new Piece(node.piece.bufferIndex, node.piece.start, newEnd, newLineFeedCnt, newLength);

        this._lastChangeBufferPos = newEnd;
        updateTreeMetadata(this, node, value.length, lf_delta);
    }

    private nodeAt(offset: number): NodePosition {
        let x = this.root;
        const cache = this._searchCache.get(offset);
        if (cache) {
            return {
                node: cache.node,
                nodeStartOffset: cache.nodeStartOffset,
                remainder: offset - cache.nodeStartOffset,
            };
        }

        let nodeStartOffset = 0;

        while (x !== SENTINEL) {
            if (x.size_left > offset) {
                x = x.left;
            } else if (x.size_left + x.piece.length >= offset) {
                nodeStartOffset += x.size_left;
                const ret = {
                    node: x,
                    remainder: offset - x.size_left,
                    nodeStartOffset,
                };
                this._searchCache.set(ret);
                return ret;
            } else {
                offset -= x.size_left + x.piece.length;
                nodeStartOffset += x.size_left + x.piece.length;
                x = x.right;
            }
        }

        return null!;
    }

    private nodeAt2(lineNumber: number, column: number): NodePosition {
        let x = this.root;
        let nodeStartOffset = 0;

        while (x !== SENTINEL) {
            if (x.left !== SENTINEL && x.lf_left >= lineNumber - 1) {
                x = x.left;
            } else if (x.lf_left + x.piece.lineFeedCnt > lineNumber - 1) {
                const prevAccumualtedValue = this.getAccumulatedValue(x, lineNumber - x.lf_left - 2);
                const accumulatedValue = this.getAccumulatedValue(x, lineNumber - x.lf_left - 1);
                nodeStartOffset += x.size_left;

                return {
                    node: x,
                    remainder: Math.min(prevAccumualtedValue + column - 1, accumulatedValue),
                    nodeStartOffset,
                };
            } else if (x.lf_left + x.piece.lineFeedCnt === lineNumber - 1) {
                const prevAccumualtedValue = this.getAccumulatedValue(x, lineNumber - x.lf_left - 2);
                if (prevAccumualtedValue + column - 1 <= x.piece.length) {
                    return {
                        node: x,
                        remainder: prevAccumualtedValue + column - 1,
                        nodeStartOffset,
                    };
                } else {
                    column -= x.piece.length - prevAccumualtedValue;
                    break;
                }
            } else {
                lineNumber -= x.lf_left + x.piece.lineFeedCnt;
                nodeStartOffset += x.size_left + x.piece.length;
                x = x.right;
            }
        }

        // search in order, to find the node contains position.column
        x = x.next();
        while (x !== SENTINEL) {
            if (x.piece.lineFeedCnt > 0) {
                const accumulatedValue = this.getAccumulatedValue(x, 0);
                const nodeStartOffset = this.offsetOfNode(x);
                return {
                    node: x,
                    remainder: Math.min(column - 1, accumulatedValue),
                    nodeStartOffset,
                };
            } else {
                if (x.piece.length >= column - 1) {
                    const nodeStartOffset = this.offsetOfNode(x);
                    return {
                        node: x,
                        remainder: column - 1,
                        nodeStartOffset,
                    };
                } else {
                    column -= x.piece.length;
                }
            }

            x = x.next();
        }

        return null!;
    }

    private nodeCharCodeAt(node: TreeNode, offset: number): number {
        if (node.piece.lineFeedCnt < 1) {
            return -1;
        }
        const buffer = this._buffers[node.piece.bufferIndex];
        const newOffset = this.offsetInBuffer(node.piece.bufferIndex, node.piece.start) + offset;
        return buffer.buffer.charCodeAt(newOffset);
    }

    private offsetOfNode(node: TreeNode): number {
        if (!node) {
            return 0;
        }
        let pos = node.size_left;
        while (node !== this.root) {
            if (node.parent.right === node) {
                pos += node.parent.size_left + node.parent.piece.length;
            }

            node = node.parent;
        }

        return pos;
    }

    // #endregion

    // #region CRLF
    private shouldCheckCRLF() {
        return !(this._EOLNormalized && this._EOL === '\n');
    }

    private startWithLF(val: string | TreeNode): boolean {
        if (typeof val === 'string') {
            return val.charCodeAt(0) === 10;
        }

        if (val === SENTINEL || val.piece.lineFeedCnt === 0) {
            return false;
        }

        const piece = val.piece;
        const lineStarts = this._buffers[piece.bufferIndex].lineStarts;
        const line = piece.start.line;
        const startOffset = lineStarts[line] + piece.start.column;
        if (line === lineStarts.length - 1) {
            // last line, so there is no line feed at the end of this line
            return false;
        }
        const nextLineOffset = lineStarts[line + 1];
        if (nextLineOffset > startOffset + 1) {
            return false;
        }
        return this._buffers[piece.bufferIndex].buffer.charCodeAt(startOffset) === 10;
    }

    private endWithCR(val: string | TreeNode): boolean {
        if (typeof val === 'string') {
            return val.charCodeAt(val.length - 1) === 13;
        }

        if (val === SENTINEL || val.piece.lineFeedCnt === 0) {
            return false;
        }

        return this.nodeCharCodeAt(val, val.piece.length - 1) === 13;
    }

    private validateCRLFWithPrevNode(nextNode: TreeNode) {
        if (this.shouldCheckCRLF() && this.startWithLF(nextNode)) {
            const node = nextNode.prev();
            if (this.endWithCR(node)) {
                this.fixCRLF(node, nextNode);
            }
        }
    }

    private validateCRLFWithNextNode(node: TreeNode) {
        if (this.shouldCheckCRLF() && this.endWithCR(node)) {
            const nextNode = node.next();
            if (this.startWithLF(nextNode)) {
                this.fixCRLF(node, nextNode);
            }
        }
    }

    private fixCRLF(prev: TreeNode, next: TreeNode) {
        const nodesToDel: TreeNode[] = [];
        // update node
        const lineStarts = this._buffers[prev.piece.bufferIndex].lineStarts;
        let newEnd: BufferCursor;
        if (prev.piece.end.column === 0) {
            // it means, last line ends with \r, not \r\n
            newEnd = {
                line: prev.piece.end.line - 1,
                column: lineStarts[prev.piece.end.line] - lineStarts[prev.piece.end.line - 1] - 1,
            };
        } else {
            // \r\n
            newEnd = { line: prev.piece.end.line, column: prev.piece.end.column - 1 };
        }

        const prevNewLength = prev.piece.length - 1;
        const prevNewLFCnt = prev.piece.lineFeedCnt - 1;
        prev.piece = new Piece(prev.piece.bufferIndex, prev.piece.start, newEnd, prevNewLFCnt, prevNewLength);

        updateTreeMetadata(this, prev, -1, -1);
        if (prev.piece.length === 0) {
            nodesToDel.push(prev);
        }

        // update nextNode
        const newStart: BufferCursor = {
            line: next.piece.start.line + 1,
            column: 0,
        };
        const newLength = next.piece.length - 1;
        const newLineFeedCnt = this.getLineFeedCnt(next.piece.bufferIndex, newStart, next.piece.end);
        next.piece = new Piece(next.piece.bufferIndex, newStart, next.piece.end, newLineFeedCnt, newLength);

        updateTreeMetadata(this, next, -1, -1);
        if (next.piece.length === 0) {
            nodesToDel.push(next);
        }

        // create new piece which contains \r\n
        const pieces = this.createNewPieces('\r\n');
        this.rbInsertRight(prev, pieces[0]);
        // delete empty nodes

        for (let i = 0; i < nodesToDel.length; i++) {
            rbDelete(this, nodesToDel[i]);
        }
    }

    private adjustCarriageReturnFromNext(value: string, node: TreeNode): boolean {
        if (this.shouldCheckCRLF() && this.endWithCR(value)) {
            const nextNode = node.next();
            if (this.startWithLF(nextNode)) {
                // move `\n` forward
                value += '\n';

                if (nextNode.piece.length === 1) {
                    rbDelete(this, nextNode);
                } else {
                    const piece = nextNode.piece;
                    const newStart: BufferCursor = {
                        line: piece.start.line + 1,
                        column: 0,
                    };
                    const newLength = piece.length - 1;
                    const newLineFeedCnt = this.getLineFeedCnt(piece.bufferIndex, newStart, piece.end);
                    nextNode.piece = new Piece(piece.bufferIndex, newStart, piece.end, newLineFeedCnt, newLength);

                    updateTreeMetadata(this, nextNode, -1, -1);
                }
                return true;
            }
        }

        return false;
    }

    // #endregion

    // #endregion

    // #region Tree operations
    iterate(node: TreeNode, callback: (node: TreeNode) => boolean): boolean {
        if (node === SENTINEL) {
            return callback(SENTINEL);
        }

        const leftRet = this.iterate(node.left, callback);
        if (!leftRet) {
            return leftRet;
        }

        return callback(node) && this.iterate(node.right, callback);
    }

    private getNodeContent(node: TreeNode) {
        if (node === SENTINEL) {
            return '';
        }
        const buffer = this._buffers[node.piece.bufferIndex];
        const piece = node.piece;
        const startOffset = this.offsetInBuffer(piece.bufferIndex, piece.start);
        const endOffset = this.offsetInBuffer(piece.bufferIndex, piece.end);
        const currentContent = buffer.buffer.substring(startOffset, endOffset);
        return currentContent;
    }

    getPieceContent(piece: Piece) {
        const buffer = this._buffers[piece.bufferIndex];
        const startOffset = this.offsetInBuffer(piece.bufferIndex, piece.start);
        const endOffset = this.offsetInBuffer(piece.bufferIndex, piece.end);
        const currentContent = buffer.buffer.substring(startOffset, endOffset);
        return currentContent;
    }

    /**
     *      node              node
     *     /  \              /  \
     *    a   b    <----   a    b
     *                         /
     *                        z
     */
    private rbInsertRight(node: TreeNode | null, p: Piece): TreeNode {
        const z = new TreeNode(p, NodeColor.Red);
        z.left = SENTINEL;
        z.right = SENTINEL;
        z.parent = SENTINEL;
        z.size_left = 0;
        z.lf_left = 0;

        const x = this.root;
        if (x === SENTINEL) {
            this.root = z;
            z.color = NodeColor.Black;
        } else if (node!.right === SENTINEL) {
            node!.right = z;
            z.parent = node!;
        } else {
            const nextNode = leftest(node!.right);
            nextNode.left = z;
            z.parent = nextNode;
        }

        fixInsert(this, z);
        return z;
    }

    /**
     *      node              node
     *     /  \              /  \
     *    a   b     ---->   a    b
     *                       \
     *                        z
     */
    private rbInsertLeft(node: TreeNode | null, p: Piece): TreeNode {
        const z = new TreeNode(p, NodeColor.Red);
        z.left = SENTINEL;
        z.right = SENTINEL;
        z.parent = SENTINEL;
        z.size_left = 0;
        z.lf_left = 0;

        if (this.root === SENTINEL) {
            this.root = z;
            z.color = NodeColor.Black;
        } else if (node!.left === SENTINEL) {
            node!.left = z;
            z.parent = node!;
        } else {
            const prevNode = righttest(node!.left); // a
            prevNode.right = z;
            z.parent = prevNode;
        }

        fixInsert(this, z);
        return z;
    }

    private getContentOfSubTree(node: TreeNode): string {
        let str = '';

        this.iterate(node, node => {
            str += this.getNodeContent(node);
            return true;
        });

        return str;
    }
    // #endregion
}