123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456 |
- /*---------------------------------------------------------------------------------------------
- * Copyright (c) Microsoft Corporation. All rights reserved.
- * Licensed under the MIT License. See License.txt in the project root for license information.
- *--------------------------------------------------------------------------------------------*/
- import * as strings from '../../../base/common/strings.js';
- import { getMapForWordSeparators } from '../controller/wordCharacterClassifier.js';
- import { Position } from '../core/position.js';
- import { Range } from '../core/range.js';
- import { FindMatch } from '../model.js';
- const LIMIT_FIND_COUNT = 999;
- export class SearchParams {
- constructor(searchString, isRegex, matchCase, wordSeparators) {
- this.searchString = searchString;
- this.isRegex = isRegex;
- this.matchCase = matchCase;
- this.wordSeparators = wordSeparators;
- }
- parseSearchRequest() {
- if (this.searchString === '') {
- return null;
- }
- // Try to create a RegExp out of the params
- let multiline;
- if (this.isRegex) {
- multiline = isMultilineRegexSource(this.searchString);
- }
- else {
- multiline = (this.searchString.indexOf('\n') >= 0);
- }
- let regex = null;
- try {
- regex = strings.createRegExp(this.searchString, this.isRegex, {
- matchCase: this.matchCase,
- wholeWord: false,
- multiline: multiline,
- global: true,
- unicode: true
- });
- }
- catch (err) {
- return null;
- }
- if (!regex) {
- return null;
- }
- let canUseSimpleSearch = (!this.isRegex && !multiline);
- if (canUseSimpleSearch && this.searchString.toLowerCase() !== this.searchString.toUpperCase()) {
- // casing might make a difference
- canUseSimpleSearch = this.matchCase;
- }
- return new SearchData(regex, this.wordSeparators ? getMapForWordSeparators(this.wordSeparators) : null, canUseSimpleSearch ? this.searchString : null);
- }
- }
- export function isMultilineRegexSource(searchString) {
- if (!searchString || searchString.length === 0) {
- return false;
- }
- for (let i = 0, len = searchString.length; i < len; i++) {
- const chCode = searchString.charCodeAt(i);
- if (chCode === 92 /* Backslash */) {
- // move to next char
- i++;
- if (i >= len) {
- // string ends with a \
- break;
- }
- const nextChCode = searchString.charCodeAt(i);
- if (nextChCode === 110 /* n */ || nextChCode === 114 /* r */ || nextChCode === 87 /* W */) {
- return true;
- }
- }
- }
- return false;
- }
- export class SearchData {
- constructor(regex, wordSeparators, simpleSearch) {
- this.regex = regex;
- this.wordSeparators = wordSeparators;
- this.simpleSearch = simpleSearch;
- }
- }
- export function createFindMatch(range, rawMatches, captureMatches) {
- if (!captureMatches) {
- return new FindMatch(range, null);
- }
- let matches = [];
- for (let i = 0, len = rawMatches.length; i < len; i++) {
- matches[i] = rawMatches[i];
- }
- return new FindMatch(range, matches);
- }
- class LineFeedCounter {
- constructor(text) {
- let lineFeedsOffsets = [];
- let lineFeedsOffsetsLen = 0;
- for (let i = 0, textLen = text.length; i < textLen; i++) {
- if (text.charCodeAt(i) === 10 /* LineFeed */) {
- lineFeedsOffsets[lineFeedsOffsetsLen++] = i;
- }
- }
- this._lineFeedsOffsets = lineFeedsOffsets;
- }
- findLineFeedCountBeforeOffset(offset) {
- const lineFeedsOffsets = this._lineFeedsOffsets;
- let min = 0;
- let max = lineFeedsOffsets.length - 1;
- if (max === -1) {
- // no line feeds
- return 0;
- }
- if (offset <= lineFeedsOffsets[0]) {
- // before first line feed
- return 0;
- }
- while (min < max) {
- const mid = min + ((max - min) / 2 >> 0);
- if (lineFeedsOffsets[mid] >= offset) {
- max = mid - 1;
- }
- else {
- if (lineFeedsOffsets[mid + 1] >= offset) {
- // bingo!
- min = mid;
- max = mid;
- }
- else {
- min = mid + 1;
- }
- }
- }
- return min + 1;
- }
- }
- export class TextModelSearch {
- static findMatches(model, searchParams, searchRange, captureMatches, limitResultCount) {
- const searchData = searchParams.parseSearchRequest();
- if (!searchData) {
- return [];
- }
- if (searchData.regex.multiline) {
- return this._doFindMatchesMultiline(model, searchRange, new Searcher(searchData.wordSeparators, searchData.regex), captureMatches, limitResultCount);
- }
- return this._doFindMatchesLineByLine(model, searchRange, searchData, captureMatches, limitResultCount);
- }
- /**
- * Multiline search always executes on the lines concatenated with \n.
- * We must therefore compensate for the count of \n in case the model is CRLF
- */
- static _getMultilineMatchRange(model, deltaOffset, text, lfCounter, matchIndex, match0) {
- let startOffset;
- let lineFeedCountBeforeMatch = 0;
- if (lfCounter) {
- lineFeedCountBeforeMatch = lfCounter.findLineFeedCountBeforeOffset(matchIndex);
- startOffset = deltaOffset + matchIndex + lineFeedCountBeforeMatch /* add as many \r as there were \n */;
- }
- else {
- startOffset = deltaOffset + matchIndex;
- }
- let endOffset;
- if (lfCounter) {
- let lineFeedCountBeforeEndOfMatch = lfCounter.findLineFeedCountBeforeOffset(matchIndex + match0.length);
- let lineFeedCountInMatch = lineFeedCountBeforeEndOfMatch - lineFeedCountBeforeMatch;
- endOffset = startOffset + match0.length + lineFeedCountInMatch /* add as many \r as there were \n */;
- }
- else {
- endOffset = startOffset + match0.length;
- }
- const startPosition = model.getPositionAt(startOffset);
- const endPosition = model.getPositionAt(endOffset);
- return new Range(startPosition.lineNumber, startPosition.column, endPosition.lineNumber, endPosition.column);
- }
- static _doFindMatchesMultiline(model, searchRange, searcher, captureMatches, limitResultCount) {
- const deltaOffset = model.getOffsetAt(searchRange.getStartPosition());
- // We always execute multiline search over the lines joined with \n
- // This makes it that \n will match the EOL for both CRLF and LF models
- // We compensate for offset errors in `_getMultilineMatchRange`
- const text = model.getValueInRange(searchRange, 1 /* LF */);
- const lfCounter = (model.getEOL() === '\r\n' ? new LineFeedCounter(text) : null);
- const result = [];
- let counter = 0;
- let m;
- searcher.reset(0);
- while ((m = searcher.next(text))) {
- result[counter++] = createFindMatch(this._getMultilineMatchRange(model, deltaOffset, text, lfCounter, m.index, m[0]), m, captureMatches);
- if (counter >= limitResultCount) {
- return result;
- }
- }
- return result;
- }
- static _doFindMatchesLineByLine(model, searchRange, searchData, captureMatches, limitResultCount) {
- const result = [];
- let resultLen = 0;
- // Early case for a search range that starts & stops on the same line number
- if (searchRange.startLineNumber === searchRange.endLineNumber) {
- const text = model.getLineContent(searchRange.startLineNumber).substring(searchRange.startColumn - 1, searchRange.endColumn - 1);
- resultLen = this._findMatchesInLine(searchData, text, searchRange.startLineNumber, searchRange.startColumn - 1, resultLen, result, captureMatches, limitResultCount);
- return result;
- }
- // Collect results from first line
- const text = model.getLineContent(searchRange.startLineNumber).substring(searchRange.startColumn - 1);
- resultLen = this._findMatchesInLine(searchData, text, searchRange.startLineNumber, searchRange.startColumn - 1, resultLen, result, captureMatches, limitResultCount);
- // Collect results from middle lines
- for (let lineNumber = searchRange.startLineNumber + 1; lineNumber < searchRange.endLineNumber && resultLen < limitResultCount; lineNumber++) {
- resultLen = this._findMatchesInLine(searchData, model.getLineContent(lineNumber), lineNumber, 0, resultLen, result, captureMatches, limitResultCount);
- }
- // Collect results from last line
- if (resultLen < limitResultCount) {
- const text = model.getLineContent(searchRange.endLineNumber).substring(0, searchRange.endColumn - 1);
- resultLen = this._findMatchesInLine(searchData, text, searchRange.endLineNumber, 0, resultLen, result, captureMatches, limitResultCount);
- }
- return result;
- }
- static _findMatchesInLine(searchData, text, lineNumber, deltaOffset, resultLen, result, captureMatches, limitResultCount) {
- 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;
- }
- const searcher = new Searcher(searchData.wordSeparators, searchData.regex);
- let m;
- // 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;
- }
- static findNextMatch(model, searchParams, searchStart, captureMatches) {
- const searchData = searchParams.parseSearchRequest();
- if (!searchData) {
- return null;
- }
- const searcher = new Searcher(searchData.wordSeparators, searchData.regex);
- if (searchData.regex.multiline) {
- return this._doFindNextMatchMultiline(model, searchStart, searcher, captureMatches);
- }
- return this._doFindNextMatchLineByLine(model, searchStart, searcher, captureMatches);
- }
- static _doFindNextMatchMultiline(model, searchStart, searcher, captureMatches) {
- const searchTextStart = new Position(searchStart.lineNumber, 1);
- const deltaOffset = model.getOffsetAt(searchTextStart);
- const lineCount = model.getLineCount();
- // We always execute multiline search over the lines joined with \n
- // This makes it that \n will match the EOL for both CRLF and LF models
- // We compensate for offset errors in `_getMultilineMatchRange`
- const text = model.getValueInRange(new Range(searchTextStart.lineNumber, searchTextStart.column, lineCount, model.getLineMaxColumn(lineCount)), 1 /* LF */);
- const lfCounter = (model.getEOL() === '\r\n' ? new LineFeedCounter(text) : null);
- searcher.reset(searchStart.column - 1);
- let m = searcher.next(text);
- if (m) {
- return createFindMatch(this._getMultilineMatchRange(model, deltaOffset, text, lfCounter, m.index, m[0]), m, captureMatches);
- }
- if (searchStart.lineNumber !== 1 || searchStart.column !== 1) {
- // Try again from the top
- return this._doFindNextMatchMultiline(model, new Position(1, 1), searcher, captureMatches);
- }
- return null;
- }
- static _doFindNextMatchLineByLine(model, searchStart, searcher, captureMatches) {
- const lineCount = model.getLineCount();
- const startLineNumber = searchStart.lineNumber;
- // Look in first line
- const text = model.getLineContent(startLineNumber);
- const r = this._findFirstMatchInLine(searcher, text, startLineNumber, searchStart.column, captureMatches);
- if (r) {
- return r;
- }
- for (let i = 1; i <= lineCount; i++) {
- const lineIndex = (startLineNumber + i - 1) % lineCount;
- const text = model.getLineContent(lineIndex + 1);
- const r = this._findFirstMatchInLine(searcher, text, lineIndex + 1, 1, captureMatches);
- if (r) {
- return r;
- }
- }
- return null;
- }
- static _findFirstMatchInLine(searcher, text, lineNumber, fromColumn, captureMatches) {
- // Set regex to search from column
- searcher.reset(fromColumn - 1);
- const m = searcher.next(text);
- if (m) {
- return createFindMatch(new Range(lineNumber, m.index + 1, lineNumber, m.index + 1 + m[0].length), m, captureMatches);
- }
- return null;
- }
- static findPreviousMatch(model, searchParams, searchStart, captureMatches) {
- const searchData = searchParams.parseSearchRequest();
- if (!searchData) {
- return null;
- }
- const searcher = new Searcher(searchData.wordSeparators, searchData.regex);
- if (searchData.regex.multiline) {
- return this._doFindPreviousMatchMultiline(model, searchStart, searcher, captureMatches);
- }
- return this._doFindPreviousMatchLineByLine(model, searchStart, searcher, captureMatches);
- }
- static _doFindPreviousMatchMultiline(model, searchStart, searcher, captureMatches) {
- const matches = this._doFindMatchesMultiline(model, new Range(1, 1, searchStart.lineNumber, searchStart.column), searcher, captureMatches, 10 * LIMIT_FIND_COUNT);
- if (matches.length > 0) {
- return matches[matches.length - 1];
- }
- const lineCount = model.getLineCount();
- if (searchStart.lineNumber !== lineCount || searchStart.column !== model.getLineMaxColumn(lineCount)) {
- // Try again with all content
- return this._doFindPreviousMatchMultiline(model, new Position(lineCount, model.getLineMaxColumn(lineCount)), searcher, captureMatches);
- }
- return null;
- }
- static _doFindPreviousMatchLineByLine(model, searchStart, searcher, captureMatches) {
- const lineCount = model.getLineCount();
- const startLineNumber = searchStart.lineNumber;
- // Look in first line
- const text = model.getLineContent(startLineNumber).substring(0, searchStart.column - 1);
- const r = this._findLastMatchInLine(searcher, text, startLineNumber, captureMatches);
- if (r) {
- return r;
- }
- for (let i = 1; i <= lineCount; i++) {
- const lineIndex = (lineCount + startLineNumber - i - 1) % lineCount;
- const text = model.getLineContent(lineIndex + 1);
- const r = this._findLastMatchInLine(searcher, text, lineIndex + 1, captureMatches);
- if (r) {
- return r;
- }
- }
- return null;
- }
- static _findLastMatchInLine(searcher, text, lineNumber, captureMatches) {
- let bestResult = null;
- let m;
- searcher.reset(0);
- while ((m = searcher.next(text))) {
- bestResult = createFindMatch(new Range(lineNumber, m.index + 1, lineNumber, m.index + 1 + m[0].length), m, captureMatches);
- }
- return bestResult;
- }
- }
- function leftIsWordBounday(wordSeparators, text, textLength, matchStartIndex, matchLength) {
- if (matchStartIndex === 0) {
- // Match starts at start of string
- return true;
- }
- const charBefore = text.charCodeAt(matchStartIndex - 1);
- if (wordSeparators.get(charBefore) !== 0 /* Regular */) {
- // The character before the match is a word separator
- return true;
- }
- if (charBefore === 13 /* CarriageReturn */ || charBefore === 10 /* LineFeed */) {
- // The character before the match is line break or carriage return.
- return true;
- }
- if (matchLength > 0) {
- const firstCharInMatch = text.charCodeAt(matchStartIndex);
- if (wordSeparators.get(firstCharInMatch) !== 0 /* Regular */) {
- // The first character inside the match is a word separator
- return true;
- }
- }
- return false;
- }
- function rightIsWordBounday(wordSeparators, text, textLength, matchStartIndex, matchLength) {
- if (matchStartIndex + matchLength === textLength) {
- // Match ends at end of string
- return true;
- }
- const charAfter = text.charCodeAt(matchStartIndex + matchLength);
- if (wordSeparators.get(charAfter) !== 0 /* Regular */) {
- // The character after the match is a word separator
- return true;
- }
- if (charAfter === 13 /* CarriageReturn */ || charAfter === 10 /* LineFeed */) {
- // The character after the match is line break or carriage return.
- return true;
- }
- if (matchLength > 0) {
- const lastCharInMatch = text.charCodeAt(matchStartIndex + matchLength - 1);
- if (wordSeparators.get(lastCharInMatch) !== 0 /* Regular */) {
- // The last character in the match is a word separator
- return true;
- }
- }
- return false;
- }
- export function isValidMatch(wordSeparators, text, textLength, matchStartIndex, matchLength) {
- return (leftIsWordBounday(wordSeparators, text, textLength, matchStartIndex, matchLength)
- && rightIsWordBounday(wordSeparators, text, textLength, matchStartIndex, matchLength));
- }
- export class Searcher {
- constructor(wordSeparators, searchRegex) {
- this._wordSeparators = wordSeparators;
- this._searchRegex = searchRegex;
- this._prevMatchStartIndex = -1;
- this._prevMatchLength = 0;
- }
- reset(lastIndex) {
- this._searchRegex.lastIndex = lastIndex;
- this._prevMatchStartIndex = -1;
- this._prevMatchLength = 0;
- }
- next(text) {
- const textLength = text.length;
- let m;
- do {
- if (this._prevMatchStartIndex + this._prevMatchLength === textLength) {
- // Reached the end of the line
- return null;
- }
- m = this._searchRegex.exec(text);
- if (!m) {
- return null;
- }
- const matchStartIndex = m.index;
- const matchLength = m[0].length;
- if (matchStartIndex === this._prevMatchStartIndex && matchLength === this._prevMatchLength) {
- if (matchLength === 0) {
- // the search result is an empty string and won't advance `regex.lastIndex`, so `regex.exec` will stuck here
- // we attempt to recover from that by advancing by two if surrogate pair found and by one otherwise
- if (strings.getNextCodePoint(text, textLength, this._searchRegex.lastIndex) > 0xFFFF) {
- this._searchRegex.lastIndex += 2;
- }
- else {
- this._searchRegex.lastIndex += 1;
- }
- continue;
- }
- // Exit early if the regex matches the same range twice
- return null;
- }
- this._prevMatchStartIndex = matchStartIndex;
- this._prevMatchLength = matchLength;
- if (!this._wordSeparators || isValidMatch(this._wordSeparators, text, textLength, matchStartIndex, matchLength)) {
- return m;
- }
- } while (m);
- return null;
- }
- }
|