CoCalc -- strings.ts

GitHub Repository: microsoft/vscode
Path: blob/main/extensions/copilot/src/util/vs/base/common/strings.ts
¹³⁴⁰⁵ views
1
//!!! DO NOT modify, this file was COPIED from 'microsoft/vscode'
2

3
/*---------------------------------------------------------------------------------------------
4
 *  Copyright (c) Microsoft Corporation. All rights reserved.
5
 *  Licensed under the MIT License. See License.txt in the project root for license information.
6
 *--------------------------------------------------------------------------------------------*/
7

8
import { LRUCachedFunction } from './cache';
9
import { CharCode } from './charCode';
10
import { Lazy } from './lazy';
11
import { Constants } from './uint';
12

13
export function isFalsyOrWhitespace(str: string | undefined): boolean {
14
	if (!str || typeof str !== 'string') {
15
		return true;
16
	}
17
	return str.trim().length === 0;
18
}
19

20
const _formatRegexp = /{(\d+)}/g;
21

22
/**
23
 * Helper to produce a string with a variable number of arguments. Insert variable segments
24
 * into the string using the {n} notation where N is the index of the argument following the string.
25
 * @param value string to which formatting is applied
26
 * @param args replacements for {n}-entries
27
 */
28
// eslint-disable-next-line @typescript-eslint/no-explicit-any
29
export function format(value: string, ...args: any[]): string {
30
	if (args.length === 0) {
31
		return value;
32
	}
33
	return value.replace(_formatRegexp, function (match, group) {
34
		const idx = parseInt(group, 10);
35
		return isNaN(idx) || idx < 0 || idx >= args.length ?
36
			match :
37
			args[idx];
38
	});
39
}
40

41
const _format2Regexp = /{([^}]+)}/g;
42

43
/**
44
 * Helper to create a string from a template and a string record.
45
 * Similar to `format` but with objects instead of positional arguments.
46
 */
47
export function format2(template: string, values: Record<string, unknown>): string {
48
	if (Object.keys(values).length === 0) {
49
		return template;
50
	}
51
	return template.replace(_format2Regexp, (match, group) => (values[group] ?? match) as string);
52
}
53

54
/**
55
 * Encodes the given value so that it can be used as literal value in html attributes.
56
 *
57
 * In other words, computes `$val`, such that `attr` in `<div attr="$val" />` has the runtime value `value`.
58
 * This prevents XSS injection.
59
 */
60
export function htmlAttributeEncodeValue(value: string): string {
61
	return value.replace(/[<>"'&]/g, ch => {
62
		switch (ch) {
63
			case '<': return '&lt;';
64
			case '>': return '&gt;';
65
			case '"': return '&quot;';
66
			case '\'': return '&apos;';
67
			case '&': return '&amp;';
68
		}
69
		return ch;
70
	});
71
}
72

73
/**
74
 * Converts HTML characters inside the string to use entities instead. Makes the string safe from
75
 * being used e.g. in HTMLElement.innerHTML.
76
 */
77
export function escape(html: string): string {
78
	return html.replace(/[<>&]/g, function (match) {
79
		switch (match) {
80
			case '<': return '&lt;';
81
			case '>': return '&gt;';
82
			case '&': return '&amp;';
83
			default: return match;
84
		}
85
	});
86
}
87

88
/**
89
 * Escapes regular expression characters in a given string
90
 */
91
export function escapeRegExpCharacters(value: string): string {
92
	return value.replace(/[\\\{\}\*\+\?\|\^\$\.\[\]\(\)]/g, '\\$&');
93
}
94

95
/**
96
 * Counts how often `substr` occurs inside `value`.
97
 */
98
export function count(value: string, substr: string): number {
99
	let result = 0;
100
	let index = value.indexOf(substr);
101
	while (index !== -1) {
102
		result++;
103
		index = value.indexOf(substr, index + substr.length);
104
	}
105
	return result;
106
}
107

108
export function truncate(value: string, maxLength: number, suffix = Ellipsis): string {
109
	if (value.length <= maxLength) {
110
		return value;
111
	}
112

113
	return `${value.substr(0, maxLength)}${suffix}`;
114
}
115

116
export function truncateMiddle(value: string, maxLength: number, suffix = Ellipsis): string {
117
	if (value.length <= maxLength) {
118
		return value;
119
	}
120

121
	const prefixLength = Math.ceil(maxLength / 2) - suffix.length / 2;
122
	const suffixLength = Math.floor(maxLength / 2) - suffix.length / 2;
123

124
	return `${value.substr(0, prefixLength)}${suffix}${value.substr(value.length - suffixLength)}`;
125
}
126

127
/**
128
 * Removes all occurrences of needle from the beginning and end of haystack.
129
 * @param haystack string to trim
130
 * @param needle the thing to trim (default is a blank)
131
 */
132
export function trim(haystack: string, needle: string = ' '): string {
133
	const trimmed = ltrim(haystack, needle);
134
	return rtrim(trimmed, needle);
135
}
136

137
/**
138
 * Removes all occurrences of needle from the beginning of haystack.
139
 * @param haystack string to trim
140
 * @param needle the thing to trim
141
 */
142
export function ltrim(haystack: string, needle: string): string {
143
	if (!haystack || !needle) {
144
		return haystack;
145
	}
146

147
	const needleLen = needle.length;
148
	let offset = 0;
149
	if (needleLen === 1) {
150
		const ch = needle.charCodeAt(0);
151
		while (offset < haystack.length && haystack.charCodeAt(offset) === ch) {
152
			offset++;
153
		}
154
	} else {
155
		while (haystack.startsWith(needle, offset)) {
156
			offset += needleLen;
157
		}
158
	}
159
	return haystack.substring(offset);
160
}
161

162
/**
163
 * Removes all occurrences of needle from the end of haystack.
164
 * @param haystack string to trim
165
 * @param needle the thing to trim
166
 */
167
export function rtrim(haystack: string, needle: string): string {
168
	if (!haystack || !needle) {
169
		return haystack;
170
	}
171

172
	const needleLen = needle.length,
173
		haystackLen = haystack.length;
174

175
	if (needleLen === 1) {
176
		let end = haystackLen;
177
		const ch = needle.charCodeAt(0);
178
		while (end > 0 && haystack.charCodeAt(end - 1) === ch) {
179
			end--;
180
		}
181
		return haystack.substring(0, end);
182
	}
183

184
	let offset = haystackLen;
185
	while (offset > 0 && haystack.endsWith(needle, offset)) {
186
		offset -= needleLen;
187
	}
188

189
	return haystack.substring(0, offset);
190
}
191

192
export function convertSimple2RegExpPattern(pattern: string): string {
193
	return pattern.replace(/[\-\\\{\}\+\?\|\^\$\.\,\[\]\(\)\#\s]/g, '\\$&').replace(/[\*]/g, '.*');
194
}
195

196
export interface RegExpOptions {
197
	matchCase?: boolean;
198
	wholeWord?: boolean;
199
	multiline?: boolean;
200
	global?: boolean;
201
	unicode?: boolean;
202
}
203

204
export function createRegExp(searchString: string, isRegex: boolean, options: RegExpOptions = {}): RegExp {
205
	if (!searchString) {
206
		throw new Error('Cannot create regex from empty string');
207
	}
208
	if (!isRegex) {
209
		searchString = escapeRegExpCharacters(searchString);
210
	}
211
	if (options.wholeWord) {
212
		if (!/\B/.test(searchString.charAt(0))) {
213
			searchString = '\\b' + searchString;
214
		}
215
		if (!/\B/.test(searchString.charAt(searchString.length - 1))) {
216
			searchString = searchString + '\\b';
217
		}
218
	}
219
	let modifiers = '';
220
	if (options.global) {
221
		modifiers += 'g';
222
	}
223
	if (!options.matchCase) {
224
		modifiers += 'i';
225
	}
226
	if (options.multiline) {
227
		modifiers += 'm';
228
	}
229
	if (options.unicode) {
230
		modifiers += 'u';
231
	}
232

233
	return new RegExp(searchString, modifiers);
234
}
235

236
export function regExpLeadsToEndlessLoop(regexp: RegExp): boolean {
237
	// Exit early if it's one of these special cases which are meant to match
238
	// against an empty string
239
	if (regexp.source === '^' || regexp.source === '^$' || regexp.source === '$' || regexp.source === '^\\s*$') {
240
		return false;
241
	}
242

243
	// We check against an empty string. If the regular expression doesn't advance
244
	// (e.g. ends in an endless loop) it will match an empty string.
245
	const match = regexp.exec('');
246
	return !!(match && regexp.lastIndex === 0);
247
}
248

249
export function joinStrings(items: (string | undefined | null | false)[], separator: string): string {
250
	return items.filter(item => item !== undefined && item !== null && item !== false).join(separator);
251
}
252

253
export function splitLines(str: string): string[] {
254
	return str.split(/\r\n|\r|\n/);
255
}
256

257
export function splitLinesIncludeSeparators(str: string): string[] {
258
	const linesWithSeparators: string[] = [];
259
	const splitLinesAndSeparators = str.split(/(\r\n|\r|\n)/);
260
	for (let i = 0; i < Math.ceil(splitLinesAndSeparators.length / 2); i++) {
261
		linesWithSeparators.push(splitLinesAndSeparators[2 * i] + (splitLinesAndSeparators[2 * i + 1] ?? ''));
262
	}
263
	return linesWithSeparators;
264
}
265

266
export function indexOfPattern(str: string, re: RegExp) {
267
	const match = re.exec(str);
268
	if (match) {
269
		return match.index;
270
	}
271
	return -1;
272
}
273

274
/**
275
 * Returns first index of the string that is not whitespace.
276
 * If string is empty or contains only whitespaces, returns -1
277
 */
278
export function firstNonWhitespaceIndex(str: string): number {
279
	for (let i = 0, len = str.length; i < len; i++) {
280
		const chCode = str.charCodeAt(i);
281
		if (chCode !== CharCode.Space && chCode !== CharCode.Tab) {
282
			return i;
283
		}
284
	}
285
	return -1;
286
}
287

288
/**
289
 * Returns the leading whitespace of the string.
290
 * If the string contains only whitespaces, returns entire string
291
 */
292
export function getLeadingWhitespace(str: string, start: number = 0, end: number = str.length): string {
293
	for (let i = start; i < end; i++) {
294
		const chCode = str.charCodeAt(i);
295
		if (chCode !== CharCode.Space && chCode !== CharCode.Tab) {
296
			return str.substring(start, i);
297
		}
298
	}
299
	return str.substring(start, end);
300
}
301

302
/**
303
 * Returns last index of the string that is not whitespace.
304
 * If string is empty or contains only whitespaces, returns -1
305
 */
306
export function lastNonWhitespaceIndex(str: string, startIndex: number = str.length - 1): number {
307
	for (let i = startIndex; i >= 0; i--) {
308
		const chCode = str.charCodeAt(i);
309
		if (chCode !== CharCode.Space && chCode !== CharCode.Tab) {
310
			return i;
311
		}
312
	}
313
	return -1;
314
}
315

316
export function getIndentationLength(str: string): number {
317
	const idx = firstNonWhitespaceIndex(str);
318
	if (idx === -1) { return str.length; }
319
	return idx;
320
}
321

322
/**
323
 * Function that works identically to String.prototype.replace, except, the
324
 * replace function is allowed to be async and return a Promise.
325
 */
326
export function replaceAsync(str: string, search: RegExp, replacer: (match: string, ...args: unknown[]) => Promise<string>): Promise<string> {
327
	const parts: (string | Promise<string>)[] = [];
328

329
	let last = 0;
330
	for (const match of str.matchAll(search)) {
331
		parts.push(str.slice(last, match.index));
332
		if (match.index === undefined) {
333
			throw new Error('match.index should be defined');
334
		}
335

336
		last = match.index + match[0].length;
337
		parts.push(replacer(match[0], ...match.slice(1), match.index, str, match.groups));
338
	}
339

340
	parts.push(str.slice(last));
341

342
	return Promise.all(parts).then(p => p.join(''));
343
}
344

345
export function compare(a: string, b: string): number {
346
	if (a < b) {
347
		return -1;
348
	} else if (a > b) {
349
		return 1;
350
	} else {
351
		return 0;
352
	}
353
}
354

355
export function compareSubstring(a: string, b: string, aStart: number = 0, aEnd: number = a.length, bStart: number = 0, bEnd: number = b.length): number {
356
	for (; aStart < aEnd && bStart < bEnd; aStart++, bStart++) {
357
		const codeA = a.charCodeAt(aStart);
358
		const codeB = b.charCodeAt(bStart);
359
		if (codeA < codeB) {
360
			return -1;
361
		} else if (codeA > codeB) {
362
			return 1;
363
		}
364
	}
365
	const aLen = aEnd - aStart;
366
	const bLen = bEnd - bStart;
367
	if (aLen < bLen) {
368
		return -1;
369
	} else if (aLen > bLen) {
370
		return 1;
371
	}
372
	return 0;
373
}
374

375
export function compareIgnoreCase(a: string, b: string): number {
376
	return compareSubstringIgnoreCase(a, b, 0, a.length, 0, b.length);
377
}
378

379
export function compareSubstringIgnoreCase(a: string, b: string, aStart: number = 0, aEnd: number = a.length, bStart: number = 0, bEnd: number = b.length): number {
380

381
	for (; aStart < aEnd && bStart < bEnd; aStart++, bStart++) {
382

383
		let codeA = a.charCodeAt(aStart);
384
		let codeB = b.charCodeAt(bStart);
385

386
		if (codeA === codeB) {
387
			// equal
388
			continue;
389
		}
390

391
		if (codeA >= 128 || codeB >= 128) {
392
			// not ASCII letters -> fallback to lower-casing strings
393
			return compareSubstring(a.toLowerCase(), b.toLowerCase(), aStart, aEnd, bStart, bEnd);
394
		}
395

396
		// mapper lower-case ascii letter onto upper-case varinats
397
		// [97-122] (lower ascii) --> [65-90] (upper ascii)
398
		if (isLowerAsciiLetter(codeA)) {
399
			codeA -= 32;
400
		}
401
		if (isLowerAsciiLetter(codeB)) {
402
			codeB -= 32;
403
		}
404

405
		// compare both code points
406
		const diff = codeA - codeB;
407
		if (diff === 0) {
408
			continue;
409
		}
410

411
		return diff;
412
	}
413

414
	const aLen = aEnd - aStart;
415
	const bLen = bEnd - bStart;
416

417
	if (aLen < bLen) {
418
		return -1;
419
	} else if (aLen > bLen) {
420
		return 1;
421
	}
422

423
	return 0;
424
}
425

426
export function isAsciiDigit(code: number): boolean {
427
	return code >= CharCode.Digit0 && code <= CharCode.Digit9;
428
}
429

430
export function isLowerAsciiLetter(code: number): boolean {
431
	return code >= CharCode.a && code <= CharCode.z;
432
}
433

434
export function isUpperAsciiLetter(code: number): boolean {
435
	return code >= CharCode.A && code <= CharCode.Z;
436
}
437

438
export function equalsIgnoreCase(a: string, b: string): boolean {
439
	return a.length === b.length && compareSubstringIgnoreCase(a, b) === 0;
440
}
441

442
export function equals(a: string | undefined, b: string | undefined, ignoreCase?: boolean): boolean {
443
	return a === b || (!!ignoreCase && a !== undefined && b !== undefined && equalsIgnoreCase(a, b));
444
}
445

446
export function startsWithIgnoreCase(str: string, candidate: string): boolean {
447
	const len = candidate.length;
448
	return len <= str.length && compareSubstringIgnoreCase(str, candidate, 0, len) === 0;
449
}
450

451
export function endsWithIgnoreCase(str: string, candidate: string): boolean {
452
	const len = str.length;
453
	const start = len - candidate.length;
454
	return start >= 0 && compareSubstringIgnoreCase(str, candidate, start, len) === 0;
455
}
456

457
/**
458
 * @returns the length of the common prefix of the two strings.
459
 */
460
export function commonPrefixLength(a: string, b: string): number {
461

462
	const len = Math.min(a.length, b.length);
463
	let i: number;
464

465
	for (i = 0; i < len; i++) {
466
		if (a.charCodeAt(i) !== b.charCodeAt(i)) {
467
			return i;
468
		}
469
	}
470

471
	return len;
472
}
473

474
/**
475
 * @returns the length of the common suffix of the two strings.
476
 */
477
export function commonSuffixLength(a: string, b: string): number {
478

479
	const len = Math.min(a.length, b.length);
480
	let i: number;
481

482
	const aLastIndex = a.length - 1;
483
	const bLastIndex = b.length - 1;
484

485
	for (i = 0; i < len; i++) {
486
		if (a.charCodeAt(aLastIndex - i) !== b.charCodeAt(bLastIndex - i)) {
487
			return i;
488
		}
489
	}
490

491
	return len;
492
}
493

494
/**
495
 * See http://en.wikipedia.org/wiki/Surrogate_pair
496
 */
497
export function isHighSurrogate(charCode: number): boolean {
498
	return (0xD800 <= charCode && charCode <= 0xDBFF);
499
}
500

501
/**
502
 * See http://en.wikipedia.org/wiki/Surrogate_pair
503
 */
504
export function isLowSurrogate(charCode: number): boolean {
505
	return (0xDC00 <= charCode && charCode <= 0xDFFF);
506
}
507

508
/**
509
 * See http://en.wikipedia.org/wiki/Surrogate_pair
510
 */
511
export function computeCodePoint(highSurrogate: number, lowSurrogate: number): number {
512
	return ((highSurrogate - 0xD800) << 10) + (lowSurrogate - 0xDC00) + 0x10000;
513
}
514

515
/**
516
 * get the code point that begins at offset `offset`
517
 */
518
export function getNextCodePoint(str: string, len: number, offset: number): number {
519
	const charCode = str.charCodeAt(offset);
520
	if (isHighSurrogate(charCode) && offset + 1 < len) {
521
		const nextCharCode = str.charCodeAt(offset + 1);
522
		if (isLowSurrogate(nextCharCode)) {
523
			return computeCodePoint(charCode, nextCharCode);
524
		}
525
	}
526
	return charCode;
527
}
528

529
/**
530
 * get the code point that ends right before offset `offset`
531
 */
532
function getPrevCodePoint(str: string, offset: number): number {
533
	const charCode = str.charCodeAt(offset - 1);
534
	if (isLowSurrogate(charCode) && offset > 1) {
535
		const prevCharCode = str.charCodeAt(offset - 2);
536
		if (isHighSurrogate(prevCharCode)) {
537
			return computeCodePoint(prevCharCode, charCode);
538
		}
539
	}
540
	return charCode;
541
}
542

543
export class CodePointIterator {
544

545
	private readonly _str: string;
546
	private readonly _len: number;
547
	private _offset: number;
548

549
	public get offset(): number {
550
		return this._offset;
551
	}
552

553
	constructor(str: string, offset: number = 0) {
554
		this._str = str;
555
		this._len = str.length;
556
		this._offset = offset;
557
	}
558

559
	public setOffset(offset: number): void {
560
		this._offset = offset;
561
	}
562

563
	public prevCodePoint(): number {
564
		const codePoint = getPrevCodePoint(this._str, this._offset);
565
		this._offset -= (codePoint >= Constants.UNICODE_SUPPLEMENTARY_PLANE_BEGIN ? 2 : 1);
566
		return codePoint;
567
	}
568

569
	public nextCodePoint(): number {
570
		const codePoint = getNextCodePoint(this._str, this._len, this._offset);
571
		this._offset += (codePoint >= Constants.UNICODE_SUPPLEMENTARY_PLANE_BEGIN ? 2 : 1);
572
		return codePoint;
573
	}
574

575
	public eol(): boolean {
576
		return (this._offset >= this._len);
577
	}
578
}
579

580
export class GraphemeIterator {
581

582
	private readonly _iterator: CodePointIterator;
583

584
	public get offset(): number {
585
		return this._iterator.offset;
586
	}
587

588
	constructor(str: string, offset: number = 0) {
589
		this._iterator = new CodePointIterator(str, offset);
590
	}
591

592
	public nextGraphemeLength(): number {
593
		const graphemeBreakTree = GraphemeBreakTree.getInstance();
594
		const iterator = this._iterator;
595
		const initialOffset = iterator.offset;
596

597
		let graphemeBreakType = graphemeBreakTree.getGraphemeBreakType(iterator.nextCodePoint());
598
		while (!iterator.eol()) {
599
			const offset = iterator.offset;
600
			const nextGraphemeBreakType = graphemeBreakTree.getGraphemeBreakType(iterator.nextCodePoint());
601
			if (breakBetweenGraphemeBreakType(graphemeBreakType, nextGraphemeBreakType)) {
602
				// move iterator back
603
				iterator.setOffset(offset);
604
				break;
605
			}
606
			graphemeBreakType = nextGraphemeBreakType;
607
		}
608
		return (iterator.offset - initialOffset);
609
	}
610

611
	public prevGraphemeLength(): number {
612
		const graphemeBreakTree = GraphemeBreakTree.getInstance();
613
		const iterator = this._iterator;
614
		const initialOffset = iterator.offset;
615

616
		let graphemeBreakType = graphemeBreakTree.getGraphemeBreakType(iterator.prevCodePoint());
617
		while (iterator.offset > 0) {
618
			const offset = iterator.offset;
619
			const prevGraphemeBreakType = graphemeBreakTree.getGraphemeBreakType(iterator.prevCodePoint());
620
			if (breakBetweenGraphemeBreakType(prevGraphemeBreakType, graphemeBreakType)) {
621
				// move iterator back
622
				iterator.setOffset(offset);
623
				break;
624
			}
625
			graphemeBreakType = prevGraphemeBreakType;
626
		}
627
		return (initialOffset - iterator.offset);
628
	}
629

630
	public eol(): boolean {
631
		return this._iterator.eol();
632
	}
633
}
634

635
export function nextCharLength(str: string, initialOffset: number): number {
636
	const iterator = new GraphemeIterator(str, initialOffset);
637
	return iterator.nextGraphemeLength();
638
}
639

640
export function prevCharLength(str: string, initialOffset: number): number {
641
	const iterator = new GraphemeIterator(str, initialOffset);
642
	return iterator.prevGraphemeLength();
643
}
644

645
export function getCharContainingOffset(str: string, offset: number): [number, number] {
646
	if (offset > 0 && isLowSurrogate(str.charCodeAt(offset))) {
647
		offset--;
648
	}
649
	const endOffset = offset + nextCharLength(str, offset);
650
	const startOffset = endOffset - prevCharLength(str, endOffset);
651
	return [startOffset, endOffset];
652
}
653

654
export function charCount(str: string): number {
655
	const iterator = new GraphemeIterator(str);
656
	let length = 0;
657
	while (!iterator.eol()) {
658
		length++;
659
		iterator.nextGraphemeLength();
660
	}
661
	return length;
662
}
663

664
let CONTAINS_RTL: RegExp | undefined = undefined;
665

666
function makeContainsRtl() {
667
	// Generated using https://github.com/alexdima/unicode-utils/blob/main/rtl-test.js
668
	return /(?:[\u05BE\u05C0\u05C3\u05C6\u05D0-\u05F4\u0608\u060B\u060D\u061B-\u064A\u066D-\u066F\u0671-\u06D5\u06E5\u06E6\u06EE\u06EF\u06FA-\u0710\u0712-\u072F\u074D-\u07A5\u07B1-\u07EA\u07F4\u07F5\u07FA\u07FE-\u0815\u081A\u0824\u0828\u0830-\u0858\u085E-\u088E\u08A0-\u08C9\u200F\uFB1D\uFB1F-\uFB28\uFB2A-\uFD3D\uFD50-\uFDC7\uFDF0-\uFDFC\uFE70-\uFEFC]|\uD802[\uDC00-\uDD1B\uDD20-\uDE00\uDE10-\uDE35\uDE40-\uDEE4\uDEEB-\uDF35\uDF40-\uDFFF]|\uD803[\uDC00-\uDD23\uDE80-\uDEA9\uDEAD-\uDF45\uDF51-\uDF81\uDF86-\uDFF6]|\uD83A[\uDC00-\uDCCF\uDD00-\uDD43\uDD4B-\uDFFF]|\uD83B[\uDC00-\uDEBB])/;
669
}
670

671
/**
672
 * Returns true if `str` contains any Unicode character that is classified as "R" or "AL".
673
 */
674
export function containsRTL(str: string): boolean {
675
	if (!CONTAINS_RTL) {
676
		CONTAINS_RTL = makeContainsRtl();
677
	}
678

679
	return CONTAINS_RTL.test(str);
680
}
681

682
const IS_BASIC_ASCII = /^[\t\n\r\x20-\x7E]*$/;
683
/**
684
 * Returns true if `str` contains only basic ASCII characters in the range 32 - 126 (including 32 and 126) or \n, \r, \t
685
 */
686
export function isBasicASCII(str: string): boolean {
687
	return IS_BASIC_ASCII.test(str);
688
}
689

690
export const UNUSUAL_LINE_TERMINATORS = /[\u2028\u2029]/; // LINE SEPARATOR (LS) or PARAGRAPH SEPARATOR (PS)
691
/**
692
 * Returns true if `str` contains unusual line terminators, like LS or PS
693
 */
694
export function containsUnusualLineTerminators(str: string): boolean {
695
	return UNUSUAL_LINE_TERMINATORS.test(str);
696
}
697

698
export function isFullWidthCharacter(charCode: number): boolean {
699
	// Do a cheap trick to better support wrapping of wide characters, treat them as 2 columns
700
	// http://jrgraphix.net/research/unicode_blocks.php
701
	//          2E80 - 2EFF   CJK Radicals Supplement
702
	//          2F00 - 2FDF   Kangxi Radicals
703
	//          2FF0 - 2FFF   Ideographic Description Characters
704
	//          3000 - 303F   CJK Symbols and Punctuation
705
	//          3040 - 309F   Hiragana
706
	//          30A0 - 30FF   Katakana
707
	//          3100 - 312F   Bopomofo
708
	//          3130 - 318F   Hangul Compatibility Jamo
709
	//          3190 - 319F   Kanbun
710
	//          31A0 - 31BF   Bopomofo Extended
711
	//          31F0 - 31FF   Katakana Phonetic Extensions
712
	//          3200 - 32FF   Enclosed CJK Letters and Months
713
	//          3300 - 33FF   CJK Compatibility
714
	//          3400 - 4DBF   CJK Unified Ideographs Extension A
715
	//          4DC0 - 4DFF   Yijing Hexagram Symbols
716
	//          4E00 - 9FFF   CJK Unified Ideographs
717
	//          A000 - A48F   Yi Syllables
718
	//          A490 - A4CF   Yi Radicals
719
	//          AC00 - D7AF   Hangul Syllables
720
	// [IGNORE] D800 - DB7F   High Surrogates
721
	// [IGNORE] DB80 - DBFF   High Private Use Surrogates
722
	// [IGNORE] DC00 - DFFF   Low Surrogates
723
	// [IGNORE] E000 - F8FF   Private Use Area
724
	//          F900 - FAFF   CJK Compatibility Ideographs
725
	// [IGNORE] FB00 - FB4F   Alphabetic Presentation Forms
726
	// [IGNORE] FB50 - FDFF   Arabic Presentation Forms-A
727
	// [IGNORE] FE00 - FE0F   Variation Selectors
728
	// [IGNORE] FE20 - FE2F   Combining Half Marks
729
	// [IGNORE] FE30 - FE4F   CJK Compatibility Forms
730
	// [IGNORE] FE50 - FE6F   Small Form Variants
731
	// [IGNORE] FE70 - FEFF   Arabic Presentation Forms-B
732
	//          FF00 - FFEF   Halfwidth and Fullwidth Forms
733
	//               [https://en.wikipedia.org/wiki/Halfwidth_and_fullwidth_forms]
734
	//               of which FF01 - FF5E fullwidth ASCII of 21 to 7E
735
	//               and FFE0 - FFE6 fullwidth symbol variants
736
	// [IGNORE]    and FF65 - FFDC halfwidth of Katakana and Hangul
737
	// [IGNORE] FFF0 - FFFF   Specials
738
	return (
739
		(charCode >= 0x2E80 && charCode <= 0xD7AF)
740
		|| (charCode >= 0xF900 && charCode <= 0xFAFF)
741
		|| (charCode >= 0xFF01 && charCode <= 0xFF5E)
742
		|| (charCode >= 0xFFE0 && charCode <= 0xFFE6)
743
	);
744
}
745

746
/**
747
 * A fast function (therefore imprecise) to check if code points are emojis.
748
 * Generated using https://github.com/alexdima/unicode-utils/blob/main/emoji-test.js
749
 */
750
export function isEmojiImprecise(x: number): boolean {
751
	return (
752
		(x >= 0x1F1E6 && x <= 0x1F1FF) || (x === 8986) || (x === 8987) || (x === 9200)
753
		|| (x === 9203) || (x >= 9728 && x <= 10175) || (x === 11088) || (x === 11093)
754
		|| (x >= 127744 && x <= 128591) || (x >= 128640 && x <= 128764)
755
		|| (x >= 128992 && x <= 129008) || (x >= 129280 && x <= 129535)
756
		|| (x >= 129648 && x <= 129782)
757
	);
758
}
759

760
/**
761
 * Given a string and a max length returns a shorted version. Shorting
762
 * happens at favorable positions - such as whitespace or punctuation characters.
763
 * The return value can be longer than the given value of `n`. Leading whitespace is always trimmed.
764
 */
765
export function lcut(text: string, n: number, prefix = ''): string {
766
	const trimmed = text.trimStart();
767

768
	if (trimmed.length < n) {
769
		return trimmed;
770
	}
771

772
	const re = /\b/g;
773
	let i = 0;
774
	while (re.test(trimmed)) {
775
		if (trimmed.length - re.lastIndex < n) {
776
			break;
777
		}
778

779
		i = re.lastIndex;
780
		re.lastIndex += 1;
781
	}
782

783
	if (i === 0) {
784
		return trimmed;
785
	}
786

787
	return prefix + trimmed.substring(i).trimStart();
788
}
789

790
/**
791
 * Given a string and a max length returns a shortened version keeping the beginning.
792
 * Shortening happens at favorable positions - such as whitespace or punctuation characters.
793
 * Trailing whitespace is always trimmed.
794
 */
795
export function rcut(text: string, n: number, suffix = ''): string {
796
	const trimmed = text.trimEnd();
797

798
	if (trimmed.length <= n) {
799
		return trimmed;
800
	}
801

802
	const re = /\b/g;
803
	let lastGoodBreak = 0;
804
	let foundBoundaryAfterN = false;
805
	while (re.test(trimmed)) {
806
		if (re.lastIndex > n) {
807
			foundBoundaryAfterN = true;
808
			break;
809
		}
810
		lastGoodBreak = re.lastIndex;
811
		re.lastIndex += 1;
812
	}
813

814
	// If no boundary was found after n, return the full trimmed string
815
	// (there's no good place to cut)
816
	if (!foundBoundaryAfterN) {
817
		return trimmed;
818
	}
819

820
	// If the only boundary <= n is at position 0 (start of string),
821
	// cutting there gives empty string, so just return the suffix
822
	if (lastGoodBreak === 0) {
823
		return suffix;
824
	}
825

826
	const result = trimmed.substring(0, lastGoodBreak).trimEnd();
827

828
	// If trimEnd removed more than half of what we cut (meaning we cut
829
	// mostly through whitespace), return the full string instead
830
	if (result.length < lastGoodBreak / 2) {
831
		return trimmed;
832
	}
833

834
	return result + suffix;
835
}
836

837
// Defacto standard: https://invisible-island.net/xterm/ctlseqs/ctlseqs.html
838
const CSI_SEQUENCE = /(?:\x1b\[|\x9b)[=?>!]?[\d;:]*["$#'* ]?[a-zA-Z@^`{}|~]/;
839
const OSC_SEQUENCE = /(?:\x1b\]|\x9d).*?(?:\x1b\\|\x07|\x9c)/;
840
const ESC_SEQUENCE = /\x1b(?:[ #%\(\)\*\+\-\.\/]?[a-zA-Z0-9\|}~@])/;
841
const CONTROL_SEQUENCES = new RegExp('(?:' + [
842
	CSI_SEQUENCE.source,
843
	OSC_SEQUENCE.source,
844
	ESC_SEQUENCE.source,
845
].join('|') + ')', 'g');
846

847
/** Iterates over parts of a string with CSI sequences */
848
export function* forAnsiStringParts(str: string) {
849
	let last = 0;
850
	for (const match of str.matchAll(CONTROL_SEQUENCES)) {
851
		if (last !== match.index) {
852
			yield { isCode: false, str: str.substring(last, match.index) };
853
		}
854

855
		yield { isCode: true, str: match[0] };
856
		last = match.index + match[0].length;
857
	}
858

859
	if (last !== str.length) {
860
		yield { isCode: false, str: str.substring(last) };
861
	}
862
}
863

864
/**
865
 * Strips ANSI escape sequences from a string.
866
 * @param str The dastringa stringo strip the ANSI escape sequences from.
867
 *
868
 * @example
869
 * removeAnsiEscapeCodes('\u001b[31mHello, World!\u001b[0m');
870
 * // 'Hello, World!'
871
 */
872
export function removeAnsiEscapeCodes(str: string): string {
873
	if (str) {
874
		str = str.replace(CONTROL_SEQUENCES, '');
875
	}
876

877
	return str;
878
}
879

880
const PROMPT_NON_PRINTABLE = /\\\[.*?\\\]/g;
881

882
/**
883
 * Strips ANSI escape sequences from a UNIX-style prompt string (eg. `$PS1`).
884
 * @param str The string to strip the ANSI escape sequences from.
885
 *
886
 * @example
887
 * removeAnsiEscapeCodesFromPrompt('\n\\[\u001b[01;34m\\]\\w\\[\u001b[00m\\]\n\\[\u001b[1;32m\\]> \\[\u001b[0m\\]');
888
 * // '\n\\w\n> '
889
 */
890
export function removeAnsiEscapeCodesFromPrompt(str: string): string {
891
	return removeAnsiEscapeCodes(str).replace(PROMPT_NON_PRINTABLE, '');
892
}
893

894

895
// -- UTF-8 BOM
896

897
export const UTF8_BOM_CHARACTER = String.fromCharCode(CharCode.UTF8_BOM);
898

899
export function startsWithUTF8BOM(str: string): boolean {
900
	return !!(str && str.length > 0 && str.charCodeAt(0) === CharCode.UTF8_BOM);
901
}
902

903
export function stripUTF8BOM(str: string): string {
904
	return startsWithUTF8BOM(str) ? str.substr(1) : str;
905
}
906

907
/**
908
 * Checks if the characters of the provided query string are included in the
909
 * target string. The characters do not have to be contiguous within the string.
910
 */
911
export function fuzzyContains(target: string, query: string): boolean {
912
	if (!target || !query) {
913
		return false; // return early if target or query are undefined
914
	}
915

916
	if (target.length < query.length) {
917
		return false; // impossible for query to be contained in target
918
	}
919

920
	const queryLen = query.length;
921
	const targetLower = target.toLowerCase();
922

923
	let index = 0;
924
	let lastIndexOf = -1;
925
	while (index < queryLen) {
926
		const indexOf = targetLower.indexOf(query[index], lastIndexOf + 1);
927
		if (indexOf < 0) {
928
			return false;
929
		}
930

931
		lastIndexOf = indexOf;
932

933
		index++;
934
	}
935

936
	return true;
937
}
938

939
export function containsUppercaseCharacter(target: string, ignoreEscapedChars = false): boolean {
940
	if (!target) {
941
		return false;
942
	}
943

944
	if (ignoreEscapedChars) {
945
		target = target.replace(/\\./g, '');
946
	}
947

948
	return target.toLowerCase() !== target;
949
}
950

951
export function uppercaseFirstLetter(str: string): string {
952
	return str.charAt(0).toUpperCase() + str.slice(1);
953
}
954

955
export function getNLines(str: string, n = 1): string {
956
	if (n === 0) {
957
		return '';
958
	}
959

960
	let idx = -1;
961
	do {
962
		idx = str.indexOf('\n', idx + 1);
963
		n--;
964
	} while (n > 0 && idx >= 0);
965

966
	if (idx === -1) {
967
		return str;
968
	}
969

970
	if (str[idx - 1] === '\r') {
971
		idx--;
972
	}
973

974
	return str.substr(0, idx);
975
}
976

977
/**
978
 * Produces 'a'-'z', followed by 'A'-'Z'... followed by 'a'-'z', etc.
979
 */
980
export function singleLetterHash(n: number): string {
981
	const LETTERS_CNT = (CharCode.Z - CharCode.A + 1);
982

983
	n = n % (2 * LETTERS_CNT);
984

985
	if (n < LETTERS_CNT) {
986
		return String.fromCharCode(CharCode.a + n);
987
	}
988

989
	return String.fromCharCode(CharCode.A + n - LETTERS_CNT);
990
}
991

992
//#region Unicode Grapheme Break
993

994
export function getGraphemeBreakType(codePoint: number): GraphemeBreakType {
995
	const graphemeBreakTree = GraphemeBreakTree.getInstance();
996
	return graphemeBreakTree.getGraphemeBreakType(codePoint);
997
}
998

999
function breakBetweenGraphemeBreakType(breakTypeA: GraphemeBreakType, breakTypeB: GraphemeBreakType): boolean {
1000
	// http://www.unicode.org/reports/tr29/#Grapheme_Cluster_Boundary_Rules
1001

1002
	// !!! Let's make the common case a bit faster
1003
	if (breakTypeA === GraphemeBreakType.Other) {
1004
		// see https://www.unicode.org/Public/13.0.0/ucd/auxiliary/GraphemeBreakTest-13.0.0d10.html#table
1005
		return (breakTypeB !== GraphemeBreakType.Extend && breakTypeB !== GraphemeBreakType.SpacingMark);
1006
	}
1007

1008
	// Do not break between a CR and LF. Otherwise, break before and after controls.
1009
	// GB3                                        CR × LF
1010
	// GB4                       (Control | CR | LF) ÷
1011
	// GB5                                           ÷ (Control | CR | LF)
1012
	if (breakTypeA === GraphemeBreakType.CR) {
1013
		if (breakTypeB === GraphemeBreakType.LF) {
1014
			return false; // GB3
1015
		}
1016
	}
1017
	if (breakTypeA === GraphemeBreakType.Control || breakTypeA === GraphemeBreakType.CR || breakTypeA === GraphemeBreakType.LF) {
1018
		return true; // GB4
1019
	}
1020
	if (breakTypeB === GraphemeBreakType.Control || breakTypeB === GraphemeBreakType.CR || breakTypeB === GraphemeBreakType.LF) {
1021
		return true; // GB5
1022
	}
1023

1024
	// Do not break Hangul syllable sequences.
1025
	// GB6                                         L × (L | V | LV | LVT)
1026
	// GB7                                  (LV | V) × (V | T)
1027
	// GB8                                 (LVT | T) × T
1028
	if (breakTypeA === GraphemeBreakType.L) {
1029
		if (breakTypeB === GraphemeBreakType.L || breakTypeB === GraphemeBreakType.V || breakTypeB === GraphemeBreakType.LV || breakTypeB === GraphemeBreakType.LVT) {
1030
			return false; // GB6
1031
		}
1032
	}
1033
	if (breakTypeA === GraphemeBreakType.LV || breakTypeA === GraphemeBreakType.V) {
1034
		if (breakTypeB === GraphemeBreakType.V || breakTypeB === GraphemeBreakType.T) {
1035
			return false; // GB7
1036
		}
1037
	}
1038
	if (breakTypeA === GraphemeBreakType.LVT || breakTypeA === GraphemeBreakType.T) {
1039
		if (breakTypeB === GraphemeBreakType.T) {
1040
			return false; // GB8
1041
		}
1042
	}
1043

1044
	// Do not break before extending characters or ZWJ.
1045
	// GB9                                           × (Extend | ZWJ)
1046
	if (breakTypeB === GraphemeBreakType.Extend || breakTypeB === GraphemeBreakType.ZWJ) {
1047
		return false; // GB9
1048
	}
1049

1050
	// The GB9a and GB9b rules only apply to extended grapheme clusters:
1051
	// Do not break before SpacingMarks, or after Prepend characters.
1052
	// GB9a                                          × SpacingMark
1053
	// GB9b                                  Prepend ×
1054
	if (breakTypeB === GraphemeBreakType.SpacingMark) {
1055
		return false; // GB9a
1056
	}
1057
	if (breakTypeA === GraphemeBreakType.Prepend) {
1058
		return false; // GB9b
1059
	}
1060

1061
	// Do not break within emoji modifier sequences or emoji zwj sequences.
1062
	// GB11    \p{Extended_Pictographic} Extend* ZWJ × \p{Extended_Pictographic}
1063
	if (breakTypeA === GraphemeBreakType.ZWJ && breakTypeB === GraphemeBreakType.Extended_Pictographic) {
1064
		// Note: we are not implementing the rule entirely here to avoid introducing states
1065
		return false; // GB11
1066
	}
1067

1068
	// GB12                          sot (RI RI)* RI × RI
1069
	// GB13                        [^RI] (RI RI)* RI × RI
1070
	if (breakTypeA === GraphemeBreakType.Regional_Indicator && breakTypeB === GraphemeBreakType.Regional_Indicator) {
1071
		// Note: we are not implementing the rule entirely here to avoid introducing states
1072
		return false; // GB12 & GB13
1073
	}
1074

1075
	// GB999                                     Any ÷ Any
1076
	return true;
1077
}
1078

1079
export const enum GraphemeBreakType {
1080
	Other = 0,
1081
	Prepend = 1,
1082
	CR = 2,
1083
	LF = 3,
1084
	Control = 4,
1085
	Extend = 5,
1086
	Regional_Indicator = 6,
1087
	SpacingMark = 7,
1088
	L = 8,
1089
	V = 9,
1090
	T = 10,
1091
	LV = 11,
1092
	LVT = 12,
1093
	ZWJ = 13,
1094
	Extended_Pictographic = 14
1095
}
1096

1097
class GraphemeBreakTree {
1098

1099
	private static _INSTANCE: GraphemeBreakTree | null = null;
1100
	public static getInstance(): GraphemeBreakTree {
1101
		if (!GraphemeBreakTree._INSTANCE) {
1102
			GraphemeBreakTree._INSTANCE = new GraphemeBreakTree();
1103
		}
1104
		return GraphemeBreakTree._INSTANCE;
1105
	}
1106

1107
	private readonly _data: number[];
1108

1109
	constructor() {
1110
		this._data = getGraphemeBreakRawData();
1111
	}
1112

1113
	public getGraphemeBreakType(codePoint: number): GraphemeBreakType {
1114
		// !!! Let's make 7bit ASCII a bit faster: 0..31
1115
		if (codePoint < 32) {
1116
			if (codePoint === CharCode.LineFeed) {
1117
				return GraphemeBreakType.LF;
1118
			}
1119
			if (codePoint === CharCode.CarriageReturn) {
1120
				return GraphemeBreakType.CR;
1121
			}
1122
			return GraphemeBreakType.Control;
1123
		}
1124
		// !!! Let's make 7bit ASCII a bit faster: 32..126
1125
		if (codePoint < 127) {
1126
			return GraphemeBreakType.Other;
1127
		}
1128

1129
		const data = this._data;
1130
		const nodeCount = data.length / 3;
1131
		let nodeIndex = 1;
1132
		while (nodeIndex <= nodeCount) {
1133
			if (codePoint < data[3 * nodeIndex]) {
1134
				// go left
1135
				nodeIndex = 2 * nodeIndex;
1136
			} else if (codePoint > data[3 * nodeIndex + 1]) {
1137
				// go right
1138
				nodeIndex = 2 * nodeIndex + 1;
1139
			} else {
1140
				// hit
1141
				return data[3 * nodeIndex + 2];
1142
			}
1143
		}
1144

1145
		return GraphemeBreakType.Other;
1146
	}
1147
}
1148

1149
function getGraphemeBreakRawData(): number[] {
1150
	// generated using https://github.com/alexdima/unicode-utils/blob/main/grapheme-break.js
1151
	return JSON.parse('[0,0,0,51229,51255,12,44061,44087,12,127462,127487,6,7083,7085,5,47645,47671,12,54813,54839,12,128678,128678,14,3270,3270,5,9919,9923,14,45853,45879,12,49437,49463,12,53021,53047,12,71216,71218,7,128398,128399,14,129360,129374,14,2519,2519,5,4448,4519,9,9742,9742,14,12336,12336,14,44957,44983,12,46749,46775,12,48541,48567,12,50333,50359,12,52125,52151,12,53917,53943,12,69888,69890,5,73018,73018,5,127990,127990,14,128558,128559,14,128759,128760,14,129653,129655,14,2027,2035,5,2891,2892,7,3761,3761,5,6683,6683,5,8293,8293,4,9825,9826,14,9999,9999,14,43452,43453,5,44509,44535,12,45405,45431,12,46301,46327,12,47197,47223,12,48093,48119,12,48989,49015,12,49885,49911,12,50781,50807,12,51677,51703,12,52573,52599,12,53469,53495,12,54365,54391,12,65279,65279,4,70471,70472,7,72145,72147,7,119173,119179,5,127799,127818,14,128240,128244,14,128512,128512,14,128652,128652,14,128721,128722,14,129292,129292,14,129445,129450,14,129734,129743,14,1476,1477,5,2366,2368,7,2750,2752,7,3076,3076,5,3415,3415,5,4141,4144,5,6109,6109,5,6964,6964,5,7394,7400,5,9197,9198,14,9770,9770,14,9877,9877,14,9968,9969,14,10084,10084,14,43052,43052,5,43713,43713,5,44285,44311,12,44733,44759,12,45181,45207,12,45629,45655,12,46077,46103,12,46525,46551,12,46973,46999,12,47421,47447,12,47869,47895,12,48317,48343,12,48765,48791,12,49213,49239,12,49661,49687,12,50109,50135,12,50557,50583,12,51005,51031,12,51453,51479,12,51901,51927,12,52349,52375,12,52797,52823,12,53245,53271,12,53693,53719,12,54141,54167,12,54589,54615,12,55037,55063,12,69506,69509,5,70191,70193,5,70841,70841,7,71463,71467,5,72330,72342,5,94031,94031,5,123628,123631,5,127763,127765,14,127941,127941,14,128043,128062,14,128302,128317,14,128465,128467,14,128539,128539,14,128640,128640,14,128662,128662,14,128703,128703,14,128745,128745,14,129004,129007,14,129329,129330,14,129402,129402,14,129483,129483,14,129686,129704,14,130048,131069,14,173,173,4,1757,1757,1,2200,2207,5,2434,2435,7,2631,2632,5,2817,2817,5,3008,3008,5,3201,3201,5,3387,3388,5,3542,3542,5,3902,3903,7,4190,4192,5,6002,6003,5,6439,6440,5,6765,6770,7,7019,7027,5,7154,7155,7,8205,8205,13,8505,8505,14,9654,9654,14,9757,9757,14,9792,9792,14,9852,9853,14,9890,9894,14,9937,9937,14,9981,9981,14,10035,10036,14,11035,11036,14,42654,42655,5,43346,43347,7,43587,43587,5,44006,44007,7,44173,44199,12,44397,44423,12,44621,44647,12,44845,44871,12,45069,45095,12,45293,45319,12,45517,45543,12,45741,45767,12,45965,45991,12,46189,46215,12,46413,46439,12,46637,46663,12,46861,46887,12,47085,47111,12,47309,47335,12,47533,47559,12,47757,47783,12,47981,48007,12,48205,48231,12,48429,48455,12,48653,48679,12,48877,48903,12,49101,49127,12,49325,49351,12,49549,49575,12,49773,49799,12,49997,50023,12,50221,50247,12,50445,50471,12,50669,50695,12,50893,50919,12,51117,51143,12,51341,51367,12,51565,51591,12,51789,51815,12,52013,52039,12,52237,52263,12,52461,52487,12,52685,52711,12,52909,52935,12,53133,53159,12,53357,53383,12,53581,53607,12,53805,53831,12,54029,54055,12,54253,54279,12,54477,54503,12,54701,54727,12,54925,54951,12,55149,55175,12,68101,68102,5,69762,69762,7,70067,70069,7,70371,70378,5,70720,70721,7,71087,71087,5,71341,71341,5,71995,71996,5,72249,72249,7,72850,72871,5,73109,73109,5,118576,118598,5,121505,121519,5,127245,127247,14,127568,127569,14,127777,127777,14,127872,127891,14,127956,127967,14,128015,128016,14,128110,128172,14,128259,128259,14,128367,128368,14,128424,128424,14,128488,128488,14,128530,128532,14,128550,128551,14,128566,128566,14,128647,128647,14,128656,128656,14,128667,128673,14,128691,128693,14,128715,128715,14,128728,128732,14,128752,128752,14,128765,128767,14,129096,129103,14,129311,129311,14,129344,129349,14,129394,129394,14,129413,129425,14,129466,129471,14,129511,129535,14,129664,129666,14,129719,129722,14,129760,129767,14,917536,917631,5,13,13,2,1160,1161,5,1564,1564,4,1807,1807,1,2085,2087,5,2307,2307,7,2382,2383,7,2497,2500,5,2563,2563,7,2677,2677,5,2763,2764,7,2879,2879,5,2914,2915,5,3021,3021,5,3142,3144,5,3263,3263,5,3285,3286,5,3398,3400,7,3530,3530,5,3633,3633,5,3864,3865,5,3974,3975,5,4155,4156,7,4229,4230,5,5909,5909,7,6078,6085,7,6277,6278,5,6451,6456,7,6744,6750,5,6846,6846,5,6972,6972,5,7074,7077,5,7146,7148,7,7222,7223,5,7416,7417,5,8234,8238,4,8417,8417,5,9000,9000,14,9203,9203,14,9730,9731,14,9748,9749,14,9762,9763,14,9776,9783,14,9800,9811,14,9831,9831,14,9872,9873,14,9882,9882,14,9900,9903,14,9929,9933,14,9941,9960,14,9974,9974,14,9989,9989,14,10006,10006,14,10062,10062,14,10160,10160,14,11647,11647,5,12953,12953,14,43019,43019,5,43232,43249,5,43443,43443,5,43567,43568,7,43696,43696,5,43765,43765,7,44013,44013,5,44117,44143,12,44229,44255,12,44341,44367,12,44453,44479,12,44565,44591,12,44677,44703,12,44789,44815,12,44901,44927,12,45013,45039,12,45125,45151,12,45237,45263,12,45349,45375,12,45461,45487,12,45573,45599,12,45685,45711,12,45797,45823,12,45909,45935,12,46021,46047,12,46133,46159,12,46245,46271,12,46357,46383,12,46469,46495,12,46581,46607,12,46693,46719,12,46805,46831,12,46917,46943,12,47029,47055,12,47141,47167,12,47253,47279,12,47365,47391,12,47477,47503,12,47589,47615,12,47701,47727,12,47813,47839,12,47925,47951,12,48037,48063,12,48149,48175,12,48261,48287,12,48373,48399,12,48485,48511,12,48597,48623,12,48709,48735,12,48821,48847,12,48933,48959,12,49045,49071,12,49157,49183,12,49269,49295,12,49381,49407,12,49493,49519,12,49605,49631,12,49717,49743,12,49829,49855,12,49941,49967,12,50053,50079,12,50165,50191,12,50277,50303,12,50389,50415,12,50501,50527,12,50613,50639,12,50725,50751,12,50837,50863,12,50949,50975,12,51061,51087,12,51173,51199,12,51285,51311,12,51397,51423,12,51509,51535,12,51621,51647,12,51733,51759,12,51845,51871,12,51957,51983,12,52069,52095,12,52181,52207,12,52293,52319,12,52405,52431,12,52517,52543,12,52629,52655,12,52741,52767,12,52853,52879,12,52965,52991,12,53077,53103,12,53189,53215,12,53301,53327,12,53413,53439,12,53525,53551,12,53637,53663,12,53749,53775,12,53861,53887,12,53973,53999,12,54085,54111,12,54197,54223,12,54309,54335,12,54421,54447,12,54533,54559,12,54645,54671,12,54757,54783,12,54869,54895,12,54981,55007,12,55093,55119,12,55243,55291,10,66045,66045,5,68325,68326,5,69688,69702,5,69817,69818,5,69957,69958,7,70089,70092,5,70198,70199,5,70462,70462,5,70502,70508,5,70750,70750,5,70846,70846,7,71100,71101,5,71230,71230,7,71351,71351,5,71737,71738,5,72000,72000,7,72160,72160,5,72273,72278,5,72752,72758,5,72882,72883,5,73031,73031,5,73461,73462,7,94192,94193,7,119149,119149,7,121403,121452,5,122915,122916,5,126980,126980,14,127358,127359,14,127535,127535,14,127759,127759,14,127771,127771,14,127792,127793,14,127825,127867,14,127897,127899,14,127945,127945,14,127985,127986,14,128000,128007,14,128021,128021,14,128066,128100,14,128184,128235,14,128249,128252,14,128266,128276,14,128335,128335,14,128379,128390,14,128407,128419,14,128444,128444,14,128481,128481,14,128499,128499,14,128526,128526,14,128536,128536,14,128543,128543,14,128556,128556,14,128564,128564,14,128577,128580,14,128643,128645,14,128649,128649,14,128654,128654,14,128660,128660,14,128664,128664,14,128675,128675,14,128686,128689,14,128695,128696,14,128705,128709,14,128717,128719,14,128725,128725,14,128736,128741,14,128747,128748,14,128755,128755,14,128762,128762,14,128981,128991,14,129009,129023,14,129160,129167,14,129296,129304,14,129320,129327,14,129340,129342,14,129356,129356,14,129388,129392,14,129399,129400,14,129404,129407,14,129432,129442,14,129454,129455,14,129473,129474,14,129485,129487,14,129648,129651,14,129659,129660,14,129671,129679,14,129709,129711,14,129728,129730,14,129751,129753,14,129776,129782,14,917505,917505,4,917760,917999,5,10,10,3,127,159,4,768,879,5,1471,1471,5,1536,1541,1,1648,1648,5,1767,1768,5,1840,1866,5,2070,2073,5,2137,2139,5,2274,2274,1,2363,2363,7,2377,2380,7,2402,2403,5,2494,2494,5,2507,2508,7,2558,2558,5,2622,2624,7,2641,2641,5,2691,2691,7,2759,2760,5,2786,2787,5,2876,2876,5,2881,2884,5,2901,2902,5,3006,3006,5,3014,3016,7,3072,3072,5,3134,3136,5,3157,3158,5,3260,3260,5,3266,3266,5,3274,3275,7,3328,3329,5,3391,3392,7,3405,3405,5,3457,3457,5,3536,3537,7,3551,3551,5,3636,3642,5,3764,3772,5,3895,3895,5,3967,3967,7,3993,4028,5,4146,4151,5,4182,4183,7,4226,4226,5,4253,4253,5,4957,4959,5,5940,5940,7,6070,6070,7,6087,6088,7,6158,6158,4,6432,6434,5,6448,6449,7,6679,6680,5,6742,6742,5,6754,6754,5,6783,6783,5,6912,6915,5,6966,6970,5,6978,6978,5,7042,7042,7,7080,7081,5,7143,7143,7,7150,7150,7,7212,7219,5,7380,7392,5,7412,7412,5,8203,8203,4,8232,8232,4,8265,8265,14,8400,8412,5,8421,8432,5,8617,8618,14,9167,9167,14,9200,9200,14,9410,9410,14,9723,9726,14,9733,9733,14,9745,9745,14,9752,9752,14,9760,9760,14,9766,9766,14,9774,9774,14,9786,9786,14,9794,9794,14,9823,9823,14,9828,9828,14,9833,9850,14,9855,9855,14,9875,9875,14,9880,9880,14,9885,9887,14,9896,9897,14,9906,9916,14,9926,9927,14,9935,9935,14,9939,9939,14,9962,9962,14,9972,9972,14,9978,9978,14,9986,9986,14,9997,9997,14,10002,10002,14,10017,10017,14,10055,10055,14,10071,10071,14,10133,10135,14,10548,10549,14,11093,11093,14,12330,12333,5,12441,12442,5,42608,42610,5,43010,43010,5,43045,43046,5,43188,43203,7,43302,43309,5,43392,43394,5,43446,43449,5,43493,43493,5,43571,43572,7,43597,43597,7,43703,43704,5,43756,43757,5,44003,44004,7,44009,44010,7,44033,44059,12,44089,44115,12,44145,44171,12,44201,44227,12,44257,44283,12,44313,44339,12,44369,44395,12,44425,44451,12,44481,44507,12,44537,44563,12,44593,44619,12,44649,44675,12,44705,44731,12,44761,44787,12,44817,44843,12,44873,44899,12,44929,44955,12,44985,45011,12,45041,45067,12,45097,45123,12,45153,45179,12,45209,45235,12,45265,45291,12,45321,45347,12,45377,45403,12,45433,45459,12,45489,45515,12,45545,45571,12,45601,45627,12,45657,45683,12,45713,45739,12,45769,45795,12,45825,45851,12,45881,45907,12,45937,45963,12,45993,46019,12,46049,46075,12,46105,46131,12,46161,46187,12,46217,46243,12,46273,46299,12,46329,46355,12,46385,46411,12,46441,46467,12,46497,46523,12,46553,46579,12,46609,46635,12,46665,46691,12,46721,46747,12,46777,46803,12,46833,46859,12,46889,46915,12,46945,46971,12,47001,47027,12,47057,47083,12,47113,47139,12,47169,47195,12,47225,47251,12,47281,47307,12,47337,47363,12,47393,47419,12,47449,47475,12,47505,47531,12,47561,47587,12,47617,47643,12,47673,47699,12,47729,47755,12,47785,47811,12,47841,47867,12,47897,47923,12,47953,47979,12,48009,48035,12,48065,48091,12,48121,48147,12,48177,48203,12,48233,48259,12,48289,48315,12,48345,48371,12,48401,48427,12,48457,48483,12,48513,48539,12,48569,48595,12,48625,48651,12,48681,48707,12,48737,48763,12,48793,48819,12,48849,48875,12,48905,48931,12,48961,48987,12,49017,49043,12,49073,49099,12,49129,49155,12,49185,49211,12,49241,49267,12,49297,49323,12,49353,49379,12,49409,49435,12,49465,49491,12,49521,49547,12,49577,49603,12,49633,49659,12,49689,49715,12,49745,49771,12,49801,49827,12,49857,49883,12,49913,49939,12,49969,49995,12,50025,50051,12,50081,50107,12,50137,50163,12,50193,50219,12,50249,50275,12,50305,50331,12,50361,50387,12,50417,50443,12,50473,50499,12,50529,50555,12,50585,50611,12,50641,50667,12,50697,50723,12,50753,50779,12,50809,50835,12,50865,50891,12,50921,50947,12,50977,51003,12,51033,51059,12,51089,51115,12,51145,51171,12,51201,51227,12,51257,51283,12,51313,51339,12,51369,51395,12,51425,51451,12,51481,51507,12,51537,51563,12,51593,51619,12,51649,51675,12,51705,51731,12,51761,51787,12,51817,51843,12,51873,51899,12,51929,51955,12,51985,52011,12,52041,52067,12,52097,52123,12,52153,52179,12,52209,52235,12,52265,52291,12,52321,52347,12,52377,52403,12,52433,52459,12,52489,52515,12,52545,52571,12,52601,52627,12,52657,52683,12,52713,52739,12,52769,52795,12,52825,52851,12,52881,52907,12,52937,52963,12,52993,53019,12,53049,53075,12,53105,53131,12,53161,53187,12,53217,53243,12,53273,53299,12,53329,53355,12,53385,53411,12,53441,53467,12,53497,53523,12,53553,53579,12,53609,53635,12,53665,53691,12,53721,53747,12,53777,53803,12,53833,53859,12,53889,53915,12,53945,53971,12,54001,54027,12,54057,54083,12,54113,54139,12,54169,54195,12,54225,54251,12,54281,54307,12,54337,54363,12,54393,54419,12,54449,54475,12,54505,54531,12,54561,54587,12,54617,54643,12,54673,54699,12,54729,54755,12,54785,54811,12,54841,54867,12,54897,54923,12,54953,54979,12,55009,55035,12,55065,55091,12,55121,55147,12,55177,55203,12,65024,65039,5,65520,65528,4,66422,66426,5,68152,68154,5,69291,69292,5,69633,69633,5,69747,69748,5,69811,69814,5,69826,69826,5,69932,69932,7,70016,70017,5,70079,70080,7,70095,70095,5,70196,70196,5,70367,70367,5,70402,70403,7,70464,70464,5,70487,70487,5,70709,70711,7,70725,70725,7,70833,70834,7,70843,70844,7,70849,70849,7,71090,71093,5,71103,71104,5,71227,71228,7,71339,71339,5,71344,71349,5,71458,71461,5,71727,71735,5,71985,71989,7,71998,71998,5,72002,72002,7,72154,72155,5,72193,72202,5,72251,72254,5,72281,72283,5,72344,72345,5,72766,72766,7,72874,72880,5,72885,72886,5,73023,73029,5,73104,73105,5,73111,73111,5,92912,92916,5,94095,94098,5,113824,113827,4,119142,119142,7,119155,119162,4,119362,119364,5,121476,121476,5,122888,122904,5,123184,123190,5,125252,125258,5,127183,127183,14,127340,127343,14,127377,127386,14,127491,127503,14,127548,127551,14,127744,127756,14,127761,127761,14,127769,127769,14,127773,127774,14,127780,127788,14,127796,127797,14,127820,127823,14,127869,127869,14,127894,127895,14,127902,127903,14,127943,127943,14,127947,127950,14,127972,127972,14,127988,127988,14,127992,127994,14,128009,128011,14,128019,128019,14,128023,128041,14,128064,128064,14,128102,128107,14,128174,128181,14,128238,128238,14,128246,128247,14,128254,128254,14,128264,128264,14,128278,128299,14,128329,128330,14,128348,128359,14,128371,128377,14,128392,128393,14,128401,128404,14,128421,128421,14,128433,128434,14,128450,128452,14,128476,128478,14,128483,128483,14,128495,128495,14,128506,128506,14,128519,128520,14,128528,128528,14,128534,128534,14,128538,128538,14,128540,128542,14,128544,128549,14,128552,128555,14,128557,128557,14,128560,128563,14,128565,128565,14,128567,128576,14,128581,128591,14,128641,128642,14,128646,128646,14,128648,128648,14,128650,128651,14,128653,128653,14,128655,128655,14,128657,128659,14,128661,128661,14,128663,128663,14,128665,128666,14,128674,128674,14,128676,128677,14,128679,128685,14,128690,128690,14,128694,128694,14,128697,128702,14,128704,128704,14,128710,128714,14,128716,128716,14,128720,128720,14,128723,128724,14,128726,128727,14,128733,128735,14,128742,128744,14,128746,128746,14,128749,128751,14,128753,128754,14,128756,128758,14,128761,128761,14,128763,128764,14,128884,128895,14,128992,129003,14,129008,129008,14,129036,129039,14,129114,129119,14,129198,129279,14,129293,129295,14,129305,129310,14,129312,129319,14,129328,129328,14,129331,129338,14,129343,129343,14,129351,129355,14,129357,129359,14,129375,129387,14,129393,129393,14,129395,129398,14,129401,129401,14,129403,129403,14,129408,129412,14,129426,129431,14,129443,129444,14,129451,129453,14,129456,129465,14,129472,129472,14,129475,129482,14,129484,129484,14,129488,129510,14,129536,129647,14,129652,129652,14,129656,129658,14,129661,129663,14,129667,129670,14,129680,129685,14,129705,129708,14,129712,129718,14,129723,129727,14,129731,129733,14,129744,129750,14,129754,129759,14,129768,129775,14,129783,129791,14,917504,917504,4,917506,917535,4,917632,917759,4,918000,921599,4,0,9,4,11,12,4,14,31,4,169,169,14,174,174,14,1155,1159,5,1425,1469,5,1473,1474,5,1479,1479,5,1552,1562,5,1611,1631,5,1750,1756,5,1759,1764,5,1770,1773,5,1809,1809,5,1958,1968,5,2045,2045,5,2075,2083,5,2089,2093,5,2192,2193,1,2250,2273,5,2275,2306,5,2362,2362,5,2364,2364,5,2369,2376,5,2381,2381,5,2385,2391,5,2433,2433,5,2492,2492,5,2495,2496,7,2503,2504,7,2509,2509,5,2530,2531,5,2561,2562,5,2620,2620,5,2625,2626,5,2635,2637,5,2672,2673,5,2689,2690,5,2748,2748,5,2753,2757,5,2761,2761,7,2765,2765,5,2810,2815,5,2818,2819,7,2878,2878,5,2880,2880,7,2887,2888,7,2893,2893,5,2903,2903,5,2946,2946,5,3007,3007,7,3009,3010,7,3018,3020,7,3031,3031,5,3073,3075,7,3132,3132,5,3137,3140,7,3146,3149,5,3170,3171,5,3202,3203,7,3262,3262,7,3264,3265,7,3267,3268,7,3271,3272,7,3276,3277,5,3298,3299,5,3330,3331,7,3390,3390,5,3393,3396,5,3402,3404,7,3406,3406,1,3426,3427,5,3458,3459,7,3535,3535,5,3538,3540,5,3544,3550,7,3570,3571,7,3635,3635,7,3655,3662,5,3763,3763,7,3784,3789,5,3893,3893,5,3897,3897,5,3953,3966,5,3968,3972,5,3981,3991,5,4038,4038,5,4145,4145,7,4153,4154,5,4157,4158,5,4184,4185,5,4209,4212,5,4228,4228,7,4237,4237,5,4352,4447,8,4520,4607,10,5906,5908,5,5938,5939,5,5970,5971,5,6068,6069,5,6071,6077,5,6086,6086,5,6089,6099,5,6155,6157,5,6159,6159,5,6313,6313,5,6435,6438,7,6441,6443,7,6450,6450,5,6457,6459,5,6681,6682,7,6741,6741,7,6743,6743,7,6752,6752,5,6757,6764,5,6771,6780,5,6832,6845,5,6847,6862,5,6916,6916,7,6965,6965,5,6971,6971,7,6973,6977,7,6979,6980,7,7040,7041,5,7073,7073,7,7078,7079,7,7082,7082,7,7142,7142,5,7144,7145,5,7149,7149,5,7151,7153,5,7204,7211,7,7220,7221,7,7376,7378,5,7393,7393,7,7405,7405,5,7415,7415,7,7616,7679,5,8204,8204,5,8206,8207,4,8233,8233,4,8252,8252,14,8288,8292,4,8294,8303,4,8413,8416,5,8418,8420,5,8482,8482,14,8596,8601,14,8986,8987,14,9096,9096,14,9193,9196,14,9199,9199,14,9201,9202,14,9208,9210,14,9642,9643,14,9664,9664,14,9728,9729,14,9732,9732,14,9735,9741,14,9743,9744,14,9746,9746,14,9750,9751,14,9753,9756,14,9758,9759,14,9761,9761,14,9764,9765,14,9767,9769,14,9771,9773,14,9775,9775,14,9784,9785,14,9787,9791,14,9793,9793,14,9795,9799,14,9812,9822,14,9824,9824,14,9827,9827,14,9829,9830,14,9832,9832,14,9851,9851,14,9854,9854,14,9856,9861,14,9874,9874,14,9876,9876,14,9878,9879,14,9881,9881,14,9883,9884,14,9888,9889,14,9895,9895,14,9898,9899,14,9904,9905,14,9917,9918,14,9924,9925,14,9928,9928,14,9934,9934,14,9936,9936,14,9938,9938,14,9940,9940,14,9961,9961,14,9963,9967,14,9970,9971,14,9973,9973,14,9975,9977,14,9979,9980,14,9982,9985,14,9987,9988,14,9992,9996,14,9998,9998,14,10000,10001,14,10004,10004,14,10013,10013,14,10024,10024,14,10052,10052,14,10060,10060,14,10067,10069,14,10083,10083,14,10085,10087,14,10145,10145,14,10175,10175,14,11013,11015,14,11088,11088,14,11503,11505,5,11744,11775,5,12334,12335,5,12349,12349,14,12951,12951,14,42607,42607,5,42612,42621,5,42736,42737,5,43014,43014,5,43043,43044,7,43047,43047,7,43136,43137,7,43204,43205,5,43263,43263,5,43335,43345,5,43360,43388,8,43395,43395,7,43444,43445,7,43450,43451,7,43454,43456,7,43561,43566,5,43569,43570,5,43573,43574,5,43596,43596,5,43644,43644,5,43698,43700,5,43710,43711,5,43755,43755,7,43758,43759,7,43766,43766,5,44005,44005,5,44008,44008,5,44012,44012,7,44032,44032,11,44060,44060,11,44088,44088,11,44116,44116,11,44144,44144,11,44172,44172,11,44200,44200,11,44228,44228,11,44256,44256,11,44284,44284,11,44312,44312,11,44340,44340,11,44368,44368,11,44396,44396,11,44424,44424,11,44452,44452,11,44480,44480,11,44508,44508,11,44536,44536,11,44564,44564,11,44592,44592,11,44620,44620,11,44648,44648,11,44676,44676,11,44704,44704,11,44732,44732,11,44760,44760,11,44788,44788,11,44816,44816,11,44844,44844,11,44872,44872,11,44900,44900,11,44928,44928,11,44956,44956,11,44984,44984,11,45012,45012,11,45040,45040,11,45068,45068,11,45096,45096,11,45124,45124,11,45152,45152,11,45180,45180,11,45208,45208,11,45236,45236,11,45264,45264,11,45292,45292,11,45320,45320,11,45348,45348,11,45376,45376,11,45404,45404,11,45432,45432,11,45460,45460,11,45488,45488,11,45516,45516,11,45544,45544,11,45572,45572,11,45600,45600,11,45628,45628,11,45656,45656,11,45684,45684,11,45712,45712,11,45740,45740,11,45768,45768,11,45796,45796,11,45824,45824,11,45852,45852,11,45880,45880,11,45908,45908,11,45936,45936,11,45964,45964,11,45992,45992,11,46020,46020,11,46048,46048,11,46076,46076,11,46104,46104,11,46132,46132,11,46160,46160,11,46188,46188,11,46216,46216,11,46244,46244,11,46272,46272,11,46300,46300,11,46328,46328,11,46356,46356,11,46384,46384,11,46412,46412,11,46440,46440,11,46468,46468,11,46496,46496,11,46524,46524,11,46552,46552,11,46580,46580,11,46608,46608,11,46636,46636,11,46664,46664,11,46692,46692,11,46720,46720,11,46748,46748,11,46776,46776,11,46804,46804,11,46832,46832,11,46860,46860,11,46888,46888,11,46916,46916,11,46944,46944,11,46972,46972,11,47000,47000,11,47028,47028,11,47056,47056,11,47084,47084,11,47112,47112,11,47140,47140,11,47168,47168,11,47196,47196,11,47224,47224,11,47252,47252,11,47280,47280,11,47308,47308,11,47336,47336,11,47364,47364,11,47392,47392,11,47420,47420,11,47448,47448,11,47476,47476,11,47504,47504,11,47532,47532,11,47560,47560,11,47588,47588,11,47616,47616,11,47644,47644,11,47672,47672,11,47700,47700,11,47728,47728,11,47756,47756,11,47784,47784,11,47812,47812,11,47840,47840,11,47868,47868,11,47896,47896,11,47924,47924,11,47952,47952,11,47980,47980,11,48008,48008,11,48036,48036,11,48064,48064,11,48092,48092,11,48120,48120,11,48148,48148,11,48176,48176,11,48204,48204,11,48232,48232,11,48260,48260,11,48288,48288,11,48316,48316,11,48344,48344,11,48372,48372,11,48400,48400,11,48428,48428,11,48456,48456,11,48484,48484,11,48512,48512,11,48540,48540,11,48568,48568,11,48596,48596,11,48624,48624,11,48652,48652,11,48680,48680,11,48708,48708,11,48736,48736,11,48764,48764,11,48792,48792,11,48820,48820,11,48848,48848,11,48876,48876,11,48904,48904,11,48932,48932,11,48960,48960,11,48988,48988,11,49016,49016,11,49044,49044,11,49072,49072,11,49100,49100,11,49128,49128,11,49156,49156,11,49184,49184,11,49212,49212,11,49240,49240,11,49268,49268,11,49296,49296,11,49324,49324,11,49352,49352,11,49380,49380,11,49408,49408,11,49436,49436,11,49464,49464,11,49492,49492,11,49520,49520,11,49548,49548,11,49576,49576,11,49604,49604,11,49632,49632,11,49660,49660,11,49688,49688,11,49716,49716,11,49744,49744,11,49772,49772,11,49800,49800,11,49828,49828,11,49856,49856,11,49884,49884,11,49912,49912,11,49940,49940,11,49968,49968,11,49996,49996,11,50024,50024,11,50052,50052,11,50080,50080,11,50108,50108,11,50136,50136,11,50164,50164,11,50192,50192,11,50220,50220,11,50248,50248,11,50276,50276,11,50304,50304,11,50332,50332,11,50360,50360,11,50388,50388,11,50416,50416,11,50444,50444,11,50472,50472,11,50500,50500,11,50528,50528,11,50556,50556,11,50584,50584,11,50612,50612,11,50640,50640,11,50668,50668,11,50696,50696,11,50724,50724,11,50752,50752,11,50780,50780,11,50808,50808,11,50836,50836,11,50864,50864,11,50892,50892,11,50920,50920,11,50948,50948,11,50976,50976,11,51004,51004,11,51032,51032,11,51060,51060,11,51088,51088,11,51116,51116,11,51144,51144,11,51172,51172,11,51200,51200,11,51228,51228,11,51256,51256,11,51284,51284,11,51312,51312,11,51340,51340,11,51368,51368,11,51396,51396,11,51424,51424,11,51452,51452,11,51480,51480,11,51508,51508,11,51536,51536,11,51564,51564,11,51592,51592,11,51620,51620,11,51648,51648,11,51676,51676,11,51704,51704,11,51732,51732,11,51760,51760,11,51788,51788,11,51816,51816,11,51844,51844,11,51872,51872,11,51900,51900,11,51928,51928,11,51956,51956,11,51984,51984,11,52012,52012,11,52040,52040,11,52068,52068,11,52096,52096,11,52124,52124,11,52152,52152,11,52180,52180,11,52208,52208,11,52236,52236,11,52264,52264,11,52292,52292,11,52320,52320,11,52348,52348,11,52376,52376,11,52404,52404,11,52432,52432,11,52460,52460,11,52488,52488,11,52516,52516,11,52544,52544,11,52572,52572,11,52600,52600,11,52628,52628,11,52656,52656,11,52684,52684,11,52712,52712,11,52740,52740,11,52768,52768,11,52796,52796,11,52824,52824,11,52852,52852,11,52880,52880,11,52908,52908,11,52936,52936,11,52964,52964,11,52992,52992,11,53020,53020,11,53048,53048,11,53076,53076,11,53104,53104,11,53132,53132,11,53160,53160,11,53188,53188,11,53216,53216,11,53244,53244,11,53272,53272,11,53300,53300,11,53328,53328,11,53356,53356,11,53384,53384,11,53412,53412,11,53440,53440,11,53468,53468,11,53496,53496,11,53524,53524,11,53552,53552,11,53580,53580,11,53608,53608,11,53636,53636,11,53664,53664,11,53692,53692,11,53720,53720,11,53748,53748,11,53776,53776,11,53804,53804,11,53832,53832,11,53860,53860,11,53888,53888,11,53916,53916,11,53944,53944,11,53972,53972,11,54000,54000,11,54028,54028,11,54056,54056,11,54084,54084,11,54112,54112,11,54140,54140,11,54168,54168,11,54196,54196,11,54224,54224,11,54252,54252,11,54280,54280,11,54308,54308,11,54336,54336,11,54364,54364,11,54392,54392,11,54420,54420,11,54448,54448,11,54476,54476,11,54504,54504,11,54532,54532,11,54560,54560,11,54588,54588,11,54616,54616,11,54644,54644,11,54672,54672,11,54700,54700,11,54728,54728,11,54756,54756,11,54784,54784,11,54812,54812,11,54840,54840,11,54868,54868,11,54896,54896,11,54924,54924,11,54952,54952,11,54980,54980,11,55008,55008,11,55036,55036,11,55064,55064,11,55092,55092,11,55120,55120,11,55148,55148,11,55176,55176,11,55216,55238,9,64286,64286,5,65056,65071,5,65438,65439,5,65529,65531,4,66272,66272,5,68097,68099,5,68108,68111,5,68159,68159,5,68900,68903,5,69446,69456,5,69632,69632,7,69634,69634,7,69744,69744,5,69759,69761,5,69808,69810,7,69815,69816,7,69821,69821,1,69837,69837,1,69927,69931,5,69933,69940,5,70003,70003,5,70018,70018,7,70070,70078,5,70082,70083,1,70094,70094,7,70188,70190,7,70194,70195,7,70197,70197,7,70206,70206,5,70368,70370,7,70400,70401,5,70459,70460,5,70463,70463,7,70465,70468,7,70475,70477,7,70498,70499,7,70512,70516,5,70712,70719,5,70722,70724,5,70726,70726,5,70832,70832,5,70835,70840,5,70842,70842,5,70845,70845,5,70847,70848,5,70850,70851,5,71088,71089,7,71096,71099,7,71102,71102,7,71132,71133,5,71219,71226,5,71229,71229,5,71231,71232,5,71340,71340,7,71342,71343,7,71350,71350,7,71453,71455,5,71462,71462,7,71724,71726,7,71736,71736,7,71984,71984,5,71991,71992,7,71997,71997,7,71999,71999,1,72001,72001,1,72003,72003,5,72148,72151,5,72156,72159,7,72164,72164,7,72243,72248,5,72250,72250,1,72263,72263,5,72279,72280,7,72324,72329,1,72343,72343,7,72751,72751,7,72760,72765,5,72767,72767,5,72873,72873,7,72881,72881,7,72884,72884,7,73009,73014,5,73020,73021,5,73030,73030,1,73098,73102,7,73107,73108,7,73110,73110,7,73459,73460,5,78896,78904,4,92976,92982,5,94033,94087,7,94180,94180,5,113821,113822,5,118528,118573,5,119141,119141,5,119143,119145,5,119150,119154,5,119163,119170,5,119210,119213,5,121344,121398,5,121461,121461,5,121499,121503,5,122880,122886,5,122907,122913,5,122918,122922,5,123566,123566,5,125136,125142,5,126976,126979,14,126981,127182,14,127184,127231,14,127279,127279,14,127344,127345,14,127374,127374,14,127405,127461,14,127489,127490,14,127514,127514,14,127538,127546,14,127561,127567,14,127570,127743,14,127757,127758,14,127760,127760,14,127762,127762,14,127766,127768,14,127770,127770,14,127772,127772,14,127775,127776,14,127778,127779,14,127789,127791,14,127794,127795,14,127798,127798,14,127819,127819,14,127824,127824,14,127868,127868,14,127870,127871,14,127892,127893,14,127896,127896,14,127900,127901,14,127904,127940,14,127942,127942,14,127944,127944,14,127946,127946,14,127951,127955,14,127968,127971,14,127973,127984,14,127987,127987,14,127989,127989,14,127991,127991,14,127995,127999,5,128008,128008,14,128012,128014,14,128017,128018,14,128020,128020,14,128022,128022,14,128042,128042,14,128063,128063,14,128065,128065,14,128101,128101,14,128108,128109,14,128173,128173,14,128182,128183,14,128236,128237,14,128239,128239,14,128245,128245,14,128248,128248,14,128253,128253,14,128255,128258,14,128260,128263,14,128265,128265,14,128277,128277,14,128300,128301,14,128326,128328,14,128331,128334,14,128336,128347,14,128360,128366,14,128369,128370,14,128378,128378,14,128391,128391,14,128394,128397,14,128400,128400,14,128405,128406,14,128420,128420,14,128422,128423,14,128425,128432,14,128435,128443,14,128445,128449,14,128453,128464,14,128468,128475,14,128479,128480,14,128482,128482,14,128484,128487,14,128489,128494,14,128496,128498,14,128500,128505,14,128507,128511,14,128513,128518,14,128521,128525,14,128527,128527,14,128529,128529,14,128533,128533,14,128535,128535,14,128537,128537,14]');
1152
}
1153

1154
//#endregion
1155

1156
/**
1157
 * Computes the offset after performing a left delete on the given string,
1158
 * while considering unicode grapheme/emoji rules.
1159
*/
1160
export function getLeftDeleteOffset(offset: number, str: string): number {
1161
	if (offset === 0) {
1162
		return 0;
1163
	}
1164

1165
	// Try to delete emoji part.
1166
	const emojiOffset = getOffsetBeforeLastEmojiComponent(offset, str);
1167
	if (emojiOffset !== undefined) {
1168
		return emojiOffset;
1169
	}
1170

1171
	// Otherwise, just skip a single code point.
1172
	const iterator = new CodePointIterator(str, offset);
1173
	iterator.prevCodePoint();
1174
	return iterator.offset;
1175
}
1176

1177
function getOffsetBeforeLastEmojiComponent(initialOffset: number, str: string): number | undefined {
1178
	// See https://www.unicode.org/reports/tr51/tr51-14.html#EBNF_and_Regex for the
1179
	// structure of emojis.
1180
	const iterator = new CodePointIterator(str, initialOffset);
1181
	let codePoint = iterator.prevCodePoint();
1182

1183
	// Skip modifiers
1184
	while ((isEmojiModifier(codePoint) || codePoint === CodePoint.emojiVariantSelector || codePoint === CodePoint.enclosingKeyCap)) {
1185
		if (iterator.offset === 0) {
1186
			// Cannot skip modifier, no preceding emoji base.
1187
			return undefined;
1188
		}
1189
		codePoint = iterator.prevCodePoint();
1190
	}
1191

1192
	// Expect base emoji
1193
	if (!isEmojiImprecise(codePoint)) {
1194
		// Unexpected code point, not a valid emoji.
1195
		return undefined;
1196
	}
1197

1198
	let resultOffset = iterator.offset;
1199

1200
	if (resultOffset > 0) {
1201
		// Skip optional ZWJ code points that combine multiple emojis.
1202
		// In theory, we should check if that ZWJ actually combines multiple emojis
1203
		// to prevent deleting ZWJs in situations we didn't account for.
1204
		const optionalZwjCodePoint = iterator.prevCodePoint();
1205
		if (optionalZwjCodePoint === CodePoint.zwj) {
1206
			resultOffset = iterator.offset;
1207
		}
1208
	}
1209

1210
	return resultOffset;
1211
}
1212

1213
function isEmojiModifier(codePoint: number): boolean {
1214
	return 0x1F3FB <= codePoint && codePoint <= 0x1F3FF;
1215
}
1216

1217
const enum CodePoint {
1218
	zwj = 0x200D,
1219

1220
	/**
1221
	 * Variation Selector-16 (VS16)
1222
	*/
1223
	emojiVariantSelector = 0xFE0F,
1224

1225
	/**
1226
	 * Combining Enclosing Keycap
1227
	 */
1228
	enclosingKeyCap = 0x20E3,
1229

1230
	space = 0x0020,
1231
}
1232

1233
export const noBreakWhitespace = '\xa0';
1234

1235
export class AmbiguousCharacters {
1236
	private static readonly ambiguousCharacterData = new Lazy<
1237
		Record<
1238
			string | '_common' | '_default',
1239
			/* code point -> ascii code point */ number[]
1240
		>
1241
	>(() => {
1242
		// Generated using https://github.com/hediet/vscode-unicode-data
1243
		// Stored as key1, value1, key2, value2, ...
1244
		return JSON.parse(
1245
			'{\"_common\":[8232,32,8233,32,5760,32,8192,32,8193,32,8194,32,8195,32,8196,32,8197,32,8198,32,8200,32,8201,32,8202,32,8287,32,8199,32,8239,32,2042,95,65101,95,65102,95,65103,95,8208,45,8209,45,8210,45,65112,45,1748,45,8259,45,727,45,8722,45,10134,45,11450,45,1549,44,1643,44,184,44,42233,44,894,59,2307,58,2691,58,1417,58,1795,58,1796,58,5868,58,65072,58,6147,58,6153,58,8282,58,1475,58,760,58,42889,58,8758,58,720,58,42237,58,451,33,11601,33,660,63,577,63,2429,63,5038,63,42731,63,119149,46,8228,46,1793,46,1794,46,42510,46,68176,46,1632,46,1776,46,42232,46,1373,96,65287,96,8219,96,1523,96,8242,96,1370,96,8175,96,65344,96,900,96,8189,96,8125,96,8127,96,8190,96,697,96,884,96,712,96,714,96,715,96,756,96,699,96,701,96,700,96,702,96,42892,96,1497,96,2036,96,2037,96,5194,96,5836,96,94033,96,94034,96,65339,91,10088,40,10098,40,12308,40,64830,40,65341,93,10089,41,10099,41,12309,41,64831,41,10100,123,119060,123,10101,125,65342,94,8270,42,1645,42,8727,42,66335,42,5941,47,8257,47,8725,47,8260,47,9585,47,10187,47,10744,47,119354,47,12755,47,12339,47,11462,47,20031,47,12035,47,65340,92,65128,92,8726,92,10189,92,10741,92,10745,92,119311,92,119355,92,12756,92,20022,92,12034,92,42872,38,708,94,710,94,5869,43,10133,43,66203,43,8249,60,10094,60,706,60,119350,60,5176,60,5810,60,5120,61,11840,61,12448,61,42239,61,8250,62,10095,62,707,62,119351,62,5171,62,94015,62,8275,126,732,126,8128,126,8764,126,65372,124,65293,45,118002,50,120784,50,120794,50,120804,50,120814,50,120824,50,130034,50,42842,50,423,50,1000,50,42564,50,5311,50,42735,50,119302,51,118003,51,120785,51,120795,51,120805,51,120815,51,120825,51,130035,51,42923,51,540,51,439,51,42858,51,11468,51,1248,51,94011,51,71882,51,118004,52,120786,52,120796,52,120806,52,120816,52,120826,52,130036,52,5070,52,71855,52,118005,53,120787,53,120797,53,120807,53,120817,53,120827,53,130037,53,444,53,71867,53,118006,54,120788,54,120798,54,120808,54,120818,54,120828,54,130038,54,11474,54,5102,54,71893,54,119314,55,118007,55,120789,55,120799,55,120809,55,120819,55,120829,55,130039,55,66770,55,71878,55,2819,56,2538,56,2666,56,125131,56,118008,56,120790,56,120800,56,120810,56,120820,56,120830,56,130040,56,547,56,546,56,66330,56,2663,57,2920,57,2541,57,3437,57,118009,57,120791,57,120801,57,120811,57,120821,57,120831,57,130041,57,42862,57,11466,57,71884,57,71852,57,71894,57,9082,97,65345,97,119834,97,119886,97,119938,97,119990,97,120042,97,120094,97,120146,97,120198,97,120250,97,120302,97,120354,97,120406,97,120458,97,593,97,945,97,120514,97,120572,97,120630,97,120688,97,120746,97,65313,65,117974,65,119808,65,119860,65,119912,65,119964,65,120016,65,120068,65,120120,65,120172,65,120224,65,120276,65,120328,65,120380,65,120432,65,913,65,120488,65,120546,65,120604,65,120662,65,120720,65,5034,65,5573,65,42222,65,94016,65,66208,65,119835,98,119887,98,119939,98,119991,98,120043,98,120095,98,120147,98,120199,98,120251,98,120303,98,120355,98,120407,98,120459,98,388,98,5071,98,5234,98,5551,98,65314,66,8492,66,117975,66,119809,66,119861,66,119913,66,120017,66,120069,66,120121,66,120173,66,120225,66,120277,66,120329,66,120381,66,120433,66,42932,66,914,66,120489,66,120547,66,120605,66,120663,66,120721,66,5108,66,5623,66,42192,66,66178,66,66209,66,66305,66,65347,99,8573,99,119836,99,119888,99,119940,99,119992,99,120044,99,120096,99,120148,99,120200,99,120252,99,120304,99,120356,99,120408,99,120460,99,7428,99,1010,99,11429,99,43951,99,66621,99,128844,67,71913,67,71922,67,65315,67,8557,67,8450,67,8493,67,117976,67,119810,67,119862,67,119914,67,119966,67,120018,67,120174,67,120226,67,120278,67,120330,67,120382,67,120434,67,1017,67,11428,67,5087,67,42202,67,66210,67,66306,67,66581,67,66844,67,8574,100,8518,100,119837,100,119889,100,119941,100,119993,100,120045,100,120097,100,120149,100,120201,100,120253,100,120305,100,120357,100,120409,100,120461,100,1281,100,5095,100,5231,100,42194,100,8558,68,8517,68,117977,68,119811,68,119863,68,119915,68,119967,68,120019,68,120071,68,120123,68,120175,68,120227,68,120279,68,120331,68,120383,68,120435,68,5024,68,5598,68,5610,68,42195,68,8494,101,65349,101,8495,101,8519,101,119838,101,119890,101,119942,101,120046,101,120098,101,120150,101,120202,101,120254,101,120306,101,120358,101,120410,101,120462,101,43826,101,1213,101,8959,69,65317,69,8496,69,117978,69,119812,69,119864,69,119916,69,120020,69,120072,69,120124,69,120176,69,120228,69,120280,69,120332,69,120384,69,120436,69,917,69,120492,69,120550,69,120608,69,120666,69,120724,69,11577,69,5036,69,42224,69,71846,69,71854,69,66182,69,119839,102,119891,102,119943,102,119995,102,120047,102,120099,102,120151,102,120203,102,120255,102,120307,102,120359,102,120411,102,120463,102,43829,102,42905,102,383,102,7837,102,1412,102,119315,70,8497,70,117979,70,119813,70,119865,70,119917,70,120021,70,120073,70,120125,70,120177,70,120229,70,120281,70,120333,70,120385,70,120437,70,42904,70,988,70,120778,70,5556,70,42205,70,71874,70,71842,70,66183,70,66213,70,66853,70,65351,103,8458,103,119840,103,119892,103,119944,103,120048,103,120100,103,120152,103,120204,103,120256,103,120308,103,120360,103,120412,103,120464,103,609,103,7555,103,397,103,1409,103,117980,71,119814,71,119866,71,119918,71,119970,71,120022,71,120074,71,120126,71,120178,71,120230,71,120282,71,120334,71,120386,71,120438,71,1292,71,5056,71,5107,71,42198,71,65352,104,8462,104,119841,104,119945,104,119997,104,120049,104,120101,104,120153,104,120205,104,120257,104,120309,104,120361,104,120413,104,120465,104,1211,104,1392,104,5058,104,65320,72,8459,72,8460,72,8461,72,117981,72,119815,72,119867,72,119919,72,120023,72,120179,72,120231,72,120283,72,120335,72,120387,72,120439,72,919,72,120494,72,120552,72,120610,72,120668,72,120726,72,11406,72,5051,72,5500,72,42215,72,66255,72,731,105,9075,105,65353,105,8560,105,8505,105,8520,105,119842,105,119894,105,119946,105,119998,105,120050,105,120102,105,120154,105,120206,105,120258,105,120310,105,120362,105,120414,105,120466,105,120484,105,618,105,617,105,953,105,8126,105,890,105,120522,105,120580,105,120638,105,120696,105,120754,105,1110,105,42567,105,1231,105,43893,105,5029,105,71875,105,65354,106,8521,106,119843,106,119895,106,119947,106,119999,106,120051,106,120103,106,120155,106,120207,106,120259,106,120311,106,120363,106,120415,106,120467,106,1011,106,1112,106,65322,74,117983,74,119817,74,119869,74,119921,74,119973,74,120025,74,120077,74,120129,74,120181,74,120233,74,120285,74,120337,74,120389,74,120441,74,42930,74,895,74,1032,74,5035,74,5261,74,42201,74,119844,107,119896,107,119948,107,120000,107,120052,107,120104,107,120156,107,120208,107,120260,107,120312,107,120364,107,120416,107,120468,107,8490,75,65323,75,117984,75,119818,75,119870,75,119922,75,119974,75,120026,75,120078,75,120130,75,120182,75,120234,75,120286,75,120338,75,120390,75,120442,75,922,75,120497,75,120555,75,120613,75,120671,75,120729,75,11412,75,5094,75,5845,75,42199,75,66840,75,1472,108,8739,73,9213,73,65512,73,1633,108,1777,73,66336,108,125127,108,118001,108,120783,73,120793,73,120803,73,120813,73,120823,73,130033,73,65321,73,8544,73,8464,73,8465,73,117982,108,119816,73,119868,73,119920,73,120024,73,120128,73,120180,73,120232,73,120284,73,120336,73,120388,73,120440,73,65356,108,8572,73,8467,108,119845,108,119897,108,119949,108,120001,108,120053,108,120105,73,120157,73,120209,73,120261,73,120313,73,120365,73,120417,73,120469,73,448,73,120496,73,120554,73,120612,73,120670,73,120728,73,11410,73,1030,73,1216,73,1493,108,1503,108,1575,108,126464,108,126592,108,65166,108,65165,108,1994,108,11599,73,5825,73,42226,73,93992,73,66186,124,66313,124,119338,76,8556,76,8466,76,117985,76,119819,76,119871,76,119923,76,120027,76,120079,76,120131,76,120183,76,120235,76,120287,76,120339,76,120391,76,120443,76,11472,76,5086,76,5290,76,42209,76,93974,76,71843,76,71858,76,66587,76,66854,76,65325,77,8559,77,8499,77,117986,77,119820,77,119872,77,119924,77,120028,77,120080,77,120132,77,120184,77,120236,77,120288,77,120340,77,120392,77,120444,77,924,77,120499,77,120557,77,120615,77,120673,77,120731,77,1018,77,11416,77,5047,77,5616,77,5846,77,42207,77,66224,77,66321,77,119847,110,119899,110,119951,110,120003,110,120055,110,120107,110,120159,110,120211,110,120263,110,120315,110,120367,110,120419,110,120471,110,1400,110,1404,110,65326,78,8469,78,117987,78,119821,78,119873,78,119925,78,119977,78,120029,78,120081,78,120185,78,120237,78,120289,78,120341,78,120393,78,120445,78,925,78,120500,78,120558,78,120616,78,120674,78,120732,78,11418,78,42208,78,66835,78,3074,111,3202,111,3330,111,3458,111,2406,111,2662,111,2790,111,3046,111,3174,111,3302,111,3430,111,3664,111,3792,111,4160,111,1637,111,1781,111,65359,111,8500,111,119848,111,119900,111,119952,111,120056,111,120108,111,120160,111,120212,111,120264,111,120316,111,120368,111,120420,111,120472,111,7439,111,7441,111,43837,111,959,111,120528,111,120586,111,120644,111,120702,111,120760,111,963,111,120532,111,120590,111,120648,111,120706,111,120764,111,11423,111,4351,111,1413,111,1505,111,1607,111,126500,111,126564,111,126596,111,65259,111,65260,111,65258,111,65257,111,1726,111,64428,111,64429,111,64427,111,64426,111,1729,111,64424,111,64425,111,64423,111,64422,111,1749,111,3360,111,4125,111,66794,111,71880,111,71895,111,66604,111,1984,79,2534,79,2918,79,12295,79,70864,79,71904,79,118000,79,120782,79,120792,79,120802,79,120812,79,120822,79,130032,79,65327,79,117988,79,119822,79,119874,79,119926,79,119978,79,120030,79,120082,79,120134,79,120186,79,120238,79,120290,79,120342,79,120394,79,120446,79,927,79,120502,79,120560,79,120618,79,120676,79,120734,79,11422,79,1365,79,11604,79,4816,79,2848,79,66754,79,42227,79,71861,79,66194,79,66219,79,66564,79,66838,79,9076,112,65360,112,119849,112,119901,112,119953,112,120005,112,120057,112,120109,112,120161,112,120213,112,120265,112,120317,112,120369,112,120421,112,120473,112,961,112,120530,112,120544,112,120588,112,120602,112,120646,112,120660,112,120704,112,120718,112,120762,112,120776,112,11427,112,65328,80,8473,80,117989,80,119823,80,119875,80,119927,80,119979,80,120031,80,120083,80,120187,80,120239,80,120291,80,120343,80,120395,80,120447,80,929,80,120504,80,120562,80,120620,80,120678,80,120736,80,11426,80,5090,80,5229,80,42193,80,66197,80,119850,113,119902,113,119954,113,120006,113,120058,113,120110,113,120162,113,120214,113,120266,113,120318,113,120370,113,120422,113,120474,113,1307,113,1379,113,1382,113,8474,81,117990,81,119824,81,119876,81,119928,81,119980,81,120032,81,120084,81,120188,81,120240,81,120292,81,120344,81,120396,81,120448,81,11605,81,119851,114,119903,114,119955,114,120007,114,120059,114,120111,114,120163,114,120215,114,120267,114,120319,114,120371,114,120423,114,120475,114,43847,114,43848,114,7462,114,11397,114,43905,114,119318,82,8475,82,8476,82,8477,82,117991,82,119825,82,119877,82,119929,82,120033,82,120189,82,120241,82,120293,82,120345,82,120397,82,120449,82,422,82,5025,82,5074,82,66740,82,5511,82,42211,82,94005,82,65363,115,119852,115,119904,115,119956,115,120008,115,120060,115,120112,115,120164,115,120216,115,120268,115,120320,115,120372,115,120424,115,120476,115,42801,115,445,115,1109,115,43946,115,71873,115,66632,115,65331,83,117992,83,119826,83,119878,83,119930,83,119982,83,120034,83,120086,83,120138,83,120190,83,120242,83,120294,83,120346,83,120398,83,120450,83,1029,83,1359,83,5077,83,5082,83,42210,83,94010,83,66198,83,66592,83,119853,116,119905,116,119957,116,120009,116,120061,116,120113,116,120165,116,120217,116,120269,116,120321,116,120373,116,120425,116,120477,116,8868,84,10201,84,128872,84,65332,84,117993,84,119827,84,119879,84,119931,84,119983,84,120035,84,120087,84,120139,84,120191,84,120243,84,120295,84,120347,84,120399,84,120451,84,932,84,120507,84,120565,84,120623,84,120681,84,120739,84,11430,84,5026,84,42196,84,93962,84,71868,84,66199,84,66225,84,66325,84,119854,117,119906,117,119958,117,120010,117,120062,117,120114,117,120166,117,120218,117,120270,117,120322,117,120374,117,120426,117,120478,117,42911,117,7452,117,43854,117,43858,117,651,117,965,117,120534,117,120592,117,120650,117,120708,117,120766,117,1405,117,66806,117,71896,117,8746,85,8899,85,117994,85,119828,85,119880,85,119932,85,119984,85,120036,85,120088,85,120140,85,120192,85,120244,85,120296,85,120348,85,120400,85,120452,85,1357,85,4608,85,66766,85,5196,85,42228,85,94018,85,71864,85,8744,118,8897,118,65366,118,8564,118,119855,118,119907,118,119959,118,120011,118,120063,118,120115,118,120167,118,120219,118,120271,118,120323,118,120375,118,120427,118,120479,118,7456,118,957,118,120526,118,120584,118,120642,118,120700,118,120758,118,1141,118,1496,118,71430,118,43945,118,71872,118,119309,86,1639,86,1783,86,8548,86,117995,86,119829,86,119881,86,119933,86,119985,86,120037,86,120089,86,120141,86,120193,86,120245,86,120297,86,120349,86,120401,86,120453,86,1140,86,11576,86,5081,86,5167,86,42719,86,42214,86,93960,86,71840,86,66845,86,623,119,119856,119,119908,119,119960,119,120012,119,120064,119,120116,119,120168,119,120220,119,120272,119,120324,119,120376,119,120428,119,120480,119,7457,119,1121,119,1309,119,1377,119,71434,119,71438,119,71439,119,43907,119,71910,87,71919,87,117996,87,119830,87,119882,87,119934,87,119986,87,120038,87,120090,87,120142,87,120194,87,120246,87,120298,87,120350,87,120402,87,120454,87,1308,87,5043,87,5076,87,42218,87,5742,120,10539,120,10540,120,10799,120,65368,120,8569,120,119857,120,119909,120,119961,120,120013,120,120065,120,120117,120,120169,120,120221,120,120273,120,120325,120,120377,120,120429,120,120481,120,5441,120,5501,120,5741,88,9587,88,66338,88,71916,88,65336,88,8553,88,117997,88,119831,88,119883,88,119935,88,119987,88,120039,88,120091,88,120143,88,120195,88,120247,88,120299,88,120351,88,120403,88,120455,88,42931,88,935,88,120510,88,120568,88,120626,88,120684,88,120742,88,11436,88,11613,88,5815,88,42219,88,66192,88,66228,88,66327,88,66855,88,611,121,7564,121,65369,121,119858,121,119910,121,119962,121,120014,121,120066,121,120118,121,120170,121,120222,121,120274,121,120326,121,120378,121,120430,121,120482,121,655,121,7935,121,43866,121,947,121,8509,121,120516,121,120574,121,120632,121,120690,121,120748,121,1199,121,4327,121,71900,121,65337,89,117998,89,119832,89,119884,89,119936,89,119988,89,120040,89,120092,89,120144,89,120196,89,120248,89,120300,89,120352,89,120404,89,120456,89,933,89,978,89,120508,89,120566,89,120624,89,120682,89,120740,89,11432,89,1198,89,5033,89,5053,89,42220,89,94019,89,71844,89,66226,89,119859,122,119911,122,119963,122,120015,122,120067,122,120119,122,120171,122,120223,122,120275,122,120327,122,120379,122,120431,122,120483,122,7458,122,43923,122,71876,122,71909,90,66293,90,65338,90,8484,90,8488,90,117999,90,119833,90,119885,90,119937,90,119989,90,120041,90,120197,90,120249,90,120301,90,120353,90,120405,90,120457,90,918,90,120493,90,120551,90,120609,90,120667,90,120725,90,5059,90,42204,90,71849,90,65282,34,65283,35,65284,36,65285,37,65286,38,65290,42,65291,43,65294,46,65295,47,65296,48,65298,50,65299,51,65300,52,65301,53,65302,54,65303,55,65304,56,65305,57,65308,60,65309,61,65310,62,65312,64,65316,68,65318,70,65319,71,65324,76,65329,81,65330,82,65333,85,65334,86,65335,87,65343,95,65346,98,65348,100,65350,102,65355,107,65357,109,65358,110,65361,113,65362,114,65364,116,65365,117,65367,119,65370,122,65371,123,65373,125,119846,109],\"_default\":[160,32,8211,45,65374,126,8218,44,65306,58,65281,33,8216,96,8217,96,8245,96,180,96,12494,47,1047,51,1073,54,1072,97,1040,65,1068,98,1042,66,1089,99,1057,67,1077,101,1045,69,1053,72,305,105,1050,75,921,73,1052,77,1086,111,1054,79,1009,112,1088,112,1056,80,1075,114,1058,84,215,120,1093,120,1061,88,1091,121,1059,89,65288,40,65289,41,65292,44,65297,49,65307,59,65311,63],\"cs\":[65374,126,8218,44,65306,58,65281,33,8216,96,8245,96,180,96,12494,47,1047,51,1073,54,1072,97,1040,65,1068,98,1042,66,1089,99,1057,67,1077,101,1045,69,1053,72,305,105,1050,75,921,73,1052,77,1086,111,1054,79,1009,112,1088,112,1056,80,1075,114,1058,84,1093,120,1061,88,1091,121,1059,89,65288,40,65289,41,65292,44,65297,49,65307,59,65311,63],\"de\":[65374,126,65306,58,65281,33,8245,96,180,96,12494,47,1047,51,1073,54,1072,97,1040,65,1068,98,1042,66,1089,99,1057,67,1077,101,1045,69,1053,72,305,105,1050,75,921,73,1052,77,1086,111,1054,79,1009,112,1088,112,1056,80,1075,114,1058,84,1093,120,1061,88,1091,121,1059,89,65288,40,65289,41,65292,44,65297,49,65307,59,65311,63],\"es\":[8211,45,65374,126,8218,44,65306,58,65281,33,8245,96,180,96,12494,47,1047,51,1073,54,1072,97,1040,65,1068,98,1042,66,1089,99,1057,67,1077,101,1045,69,1053,72,305,105,1050,75,1052,77,1086,111,1054,79,1009,112,1088,112,1056,80,1075,114,1058,84,215,120,1093,120,1061,88,1091,121,1059,89,65288,40,65289,41,65292,44,65297,49,65307,59,65311,63],\"fr\":[65374,126,8218,44,65306,58,65281,33,8216,96,8245,96,12494,47,1047,51,1073,54,1072,97,1040,65,1068,98,1042,66,1089,99,1057,67,1077,101,1045,69,1053,72,305,105,1050,75,921,73,1052,77,1086,111,1054,79,1009,112,1088,112,1056,80,1075,114,1058,84,215,120,1093,120,1061,88,1091,121,1059,89,65288,40,65289,41,65292,44,65297,49,65307,59,65311,63],\"it\":[160,32,8211,45,65374,126,8218,44,65306,58,65281,33,8245,96,180,96,12494,47,1047,51,1073,54,1072,97,1040,65,1068,98,1042,66,1089,99,1057,67,1077,101,1045,69,1053,72,305,105,1050,75,921,73,1052,77,1086,111,1054,79,1009,112,1088,112,1056,80,1075,114,1058,84,215,120,1093,120,1061,88,1091,121,1059,89,65288,40,65289,41,65292,44,65297,49,65307,59,65311,63],\"ja\":[8211,45,8218,44,65281,33,8216,96,8245,96,180,96,1047,51,1073,54,1072,97,1040,65,1068,98,1042,66,1089,99,1057,67,1077,101,1045,69,1053,72,305,105,1050,75,921,73,1052,77,1086,111,1054,79,1009,112,1088,112,1056,80,1075,114,1058,84,215,120,1093,120,1061,88,1091,121,1059,89,65292,44,65297,49,65307,59],\"ko\":[8211,45,65374,126,8218,44,65306,58,65281,33,8245,96,180,96,12494,47,1047,51,1073,54,1072,97,1040,65,1068,98,1042,66,1089,99,1057,67,1077,101,1045,69,1053,72,305,105,1050,75,921,73,1052,77,1086,111,1054,79,1009,112,1088,112,1056,80,1075,114,1058,84,215,120,1093,120,1061,88,1091,121,1059,89,65288,40,65289,41,65292,44,65297,49,65307,59,65311,63],\"pl\":[65374,126,65306,58,65281,33,8216,96,8245,96,180,96,12494,47,1047,51,1073,54,1072,97,1040,65,1068,98,1042,66,1089,99,1057,67,1077,101,1045,69,1053,72,305,105,1050,75,921,73,1052,77,1086,111,1054,79,1009,112,1088,112,1056,80,1075,114,1058,84,215,120,1093,120,1061,88,1091,121,1059,89,65288,40,65289,41,65292,44,65297,49,65307,59,65311,63],\"pt-BR\":[65374,126,8218,44,65306,58,65281,33,8216,96,8245,96,180,96,12494,47,1047,51,1073,54,1072,97,1040,65,1068,98,1042,66,1089,99,1057,67,1077,101,1045,69,1053,72,305,105,1050,75,921,73,1052,77,1086,111,1054,79,1009,112,1088,112,1056,80,1075,114,1058,84,215,120,1093,120,1061,88,1091,121,1059,89,65288,40,65289,41,65292,44,65297,49,65307,59,65311,63],\"qps-ploc\":[160,32,8211,45,65374,126,8218,44,65306,58,65281,33,8216,96,8245,96,180,96,12494,47,1047,51,1073,54,1072,97,1040,65,1068,98,1042,66,1089,99,1057,67,1077,101,1045,69,1053,72,305,105,1050,75,921,73,1052,77,1086,111,1054,79,1088,112,1056,80,1075,114,1058,84,215,120,1093,120,1061,88,1091,121,1059,89,65288,40,65289,41,65292,44,65297,49,65307,59,65311,63],\"ru\":[65374,126,8218,44,65306,58,65281,33,8216,96,8245,96,180,96,12494,47,305,105,921,73,1009,112,215,120,65288,40,65289,41,65292,44,65297,49,65307,59,65311,63],\"tr\":[160,32,8211,45,65374,126,8218,44,65306,58,65281,33,8245,96,180,96,12494,47,1047,51,1073,54,1072,97,1040,65,1068,98,1042,66,1089,99,1057,67,1077,101,1045,69,1053,72,1050,75,921,73,1052,77,1086,111,1054,79,1009,112,1088,112,1056,80,1075,114,1058,84,215,120,1093,120,1061,88,1091,121,1059,89,65288,40,65289,41,65292,44,65297,49,65307,59,65311,63],\"zh-hans\":[160,32,65374,126,8218,44,8245,96,180,96,12494,47,1047,51,1073,54,1072,97,1040,65,1068,98,1042,66,1089,99,1057,67,1077,101,1045,69,1053,72,305,105,1050,75,921,73,1052,77,1086,111,1054,79,1009,112,1088,112,1056,80,1075,114,1058,84,215,120,1093,120,1061,88,1091,121,1059,89,65297,49],\"zh-hant\":[8211,45,65374,126,8218,44,180,96,12494,47,1047,51,1073,54,1072,97,1040,65,1068,98,1042,66,1089,99,1057,67,1077,101,1045,69,1053,72,305,105,1050,75,921,73,1052,77,1086,111,1054,79,1009,112,1088,112,1056,80,1075,114,1058,84,215,120,1093,120,1061,88,1091,121,1059,89]}'
1246
		);
1247
	});
1248

1249
	private static readonly cache = new LRUCachedFunction<string, AmbiguousCharacters>((localesStr) => {
1250
		const locales = localesStr.split(',');
1251

1252
		function arrayToMap(arr: number[]): Map<number, number> {
1253
			const result = new Map<number, number>();
1254
			for (let i = 0; i < arr.length; i += 2) {
1255
				result.set(arr[i], arr[i + 1]);
1256
			}
1257
			return result;
1258
		}
1259

1260
		function mergeMaps(
1261
			map1: Map<number, number>,
1262
			map2: Map<number, number>
1263
		): Map<number, number> {
1264
			const result = new Map<number, number>(map1);
1265
			for (const [key, value] of map2) {
1266
				result.set(key, value);
1267
			}
1268
			return result;
1269
		}
1270

1271
		function intersectMaps(
1272
			map1: Map<number, number> | undefined,
1273
			map2: Map<number, number>
1274
		) {
1275
			if (!map1) {
1276
				return map2;
1277
			}
1278
			const result = new Map<number, number>();
1279
			for (const [key, value] of map1) {
1280
				if (map2.has(key)) {
1281
					result.set(key, value);
1282
				}
1283
			}
1284
			return result;
1285
		}
1286

1287
		const data = this.ambiguousCharacterData.value;
1288

1289
		let filteredLocales = locales.filter(
1290
			(l) => !l.startsWith('_') && Object.hasOwn(data, l)
1291
		);
1292
		if (filteredLocales.length === 0) {
1293
			filteredLocales = ['_default'];
1294
		}
1295

1296
		let languageSpecificMap: Map<number, number> | undefined = undefined;
1297
		for (const locale of filteredLocales) {
1298
			const map = arrayToMap(data[locale]);
1299
			languageSpecificMap = intersectMaps(languageSpecificMap, map);
1300
		}
1301

1302
		const commonMap = arrayToMap(data['_common']);
1303
		const map = mergeMaps(commonMap, languageSpecificMap!);
1304

1305
		return new AmbiguousCharacters(map);
1306
	});
1307

1308
	public static getInstance(locales: Iterable<string>): AmbiguousCharacters {
1309
		return AmbiguousCharacters.cache.get(Array.from(locales).join(','));
1310
	}
1311

1312
	private static _locales = new Lazy<string[]>(() =>
1313
		Object.keys(AmbiguousCharacters.ambiguousCharacterData.value).filter(
1314
			(k) => !k.startsWith('_')
1315
		)
1316
	);
1317
	public static getLocales(): string[] {
1318
		return AmbiguousCharacters._locales.value;
1319
	}
1320

1321
	private constructor(
1322
		private readonly confusableDictionary: Map<number, number>
1323
	) { }
1324

1325
	public isAmbiguous(codePoint: number): boolean {
1326
		return this.confusableDictionary.has(codePoint);
1327
	}
1328

1329
	public containsAmbiguousCharacter(str: string): boolean {
1330
		for (let i = 0; i < str.length; i++) {
1331
			const codePoint = str.codePointAt(i);
1332
			if (typeof codePoint === 'number' && this.isAmbiguous(codePoint)) {
1333
				return true;
1334
			}
1335
		}
1336
		return false;
1337
	}
1338

1339
	/**
1340
	 * Returns the non basic ASCII code point that the given code point can be confused,
1341
	 * or undefined if such code point does note exist.
1342
	 */
1343
	public getPrimaryConfusable(codePoint: number): number | undefined {
1344
		return this.confusableDictionary.get(codePoint);
1345
	}
1346

1347
	public getConfusableCodePoints(): ReadonlySet<number> {
1348
		return new Set(this.confusableDictionary.keys());
1349
	}
1350
}
1351

1352
export class InvisibleCharacters {
1353
	private static getRawData(): Record<string | '_common', number[]> {
1354
		// Generated using https://github.com/hediet/vscode-unicode-data
1355
		return JSON.parse('{\"_common\":[11,12,13,127,847,1564,4447,4448,6068,6069,6155,6156,6157,6158,7355,7356,8192,8193,8194,8195,8196,8197,8198,8199,8200,8201,8202,8204,8205,8206,8207,8234,8235,8236,8237,8238,8239,8287,8288,8289,8290,8291,8292,8293,8294,8295,8296,8297,8298,8299,8300,8301,8302,8303,10240,12644,65024,65025,65026,65027,65028,65029,65030,65031,65032,65033,65034,65035,65036,65037,65038,65039,65279,65440,65520,65521,65522,65523,65524,65525,65526,65527,65528,65532,78844,119155,119156,119157,119158,119159,119160,119161,119162,917504,917505,917506,917507,917508,917509,917510,917511,917512,917513,917514,917515,917516,917517,917518,917519,917520,917521,917522,917523,917524,917525,917526,917527,917528,917529,917530,917531,917532,917533,917534,917535,917536,917537,917538,917539,917540,917541,917542,917543,917544,917545,917546,917547,917548,917549,917550,917551,917552,917553,917554,917555,917556,917557,917558,917559,917560,917561,917562,917563,917564,917565,917566,917567,917568,917569,917570,917571,917572,917573,917574,917575,917576,917577,917578,917579,917580,917581,917582,917583,917584,917585,917586,917587,917588,917589,917590,917591,917592,917593,917594,917595,917596,917597,917598,917599,917600,917601,917602,917603,917604,917605,917606,917607,917608,917609,917610,917611,917612,917613,917614,917615,917616,917617,917618,917619,917620,917621,917622,917623,917624,917625,917626,917627,917628,917629,917630,917631,917760,917761,917762,917763,917764,917765,917766,917767,917768,917769,917770,917771,917772,917773,917774,917775,917776,917777,917778,917779,917780,917781,917782,917783,917784,917785,917786,917787,917788,917789,917790,917791,917792,917793,917794,917795,917796,917797,917798,917799,917800,917801,917802,917803,917804,917805,917806,917807,917808,917809,917810,917811,917812,917813,917814,917815,917816,917817,917818,917819,917820,917821,917822,917823,917824,917825,917826,917827,917828,917829,917830,917831,917832,917833,917834,917835,917836,917837,917838,917839,917840,917841,917842,917843,917844,917845,917846,917847,917848,917849,917850,917851,917852,917853,917854,917855,917856,917857,917858,917859,917860,917861,917862,917863,917864,917865,917866,917867,917868,917869,917870,917871,917872,917873,917874,917875,917876,917877,917878,917879,917880,917881,917882,917883,917884,917885,917886,917887,917888,917889,917890,917891,917892,917893,917894,917895,917896,917897,917898,917899,917900,917901,917902,917903,917904,917905,917906,917907,917908,917909,917910,917911,917912,917913,917914,917915,917916,917917,917918,917919,917920,917921,917922,917923,917924,917925,917926,917927,917928,917929,917930,917931,917932,917933,917934,917935,917936,917937,917938,917939,917940,917941,917942,917943,917944,917945,917946,917947,917948,917949,917950,917951,917952,917953,917954,917955,917956,917957,917958,917959,917960,917961,917962,917963,917964,917965,917966,917967,917968,917969,917970,917971,917972,917973,917974,917975,917976,917977,917978,917979,917980,917981,917982,917983,917984,917985,917986,917987,917988,917989,917990,917991,917992,917993,917994,917995,917996,917997,917998,917999],\"cs\":[173,8203,12288],\"de\":[173,8203,12288],\"es\":[8203,12288],\"fr\":[173,8203,12288],\"it\":[160,173,12288],\"ja\":[173],\"ko\":[173,12288],\"pl\":[173,8203,12288],\"pt-BR\":[173,8203,12288],\"qps-ploc\":[160,173,8203,12288],\"ru\":[173,12288],\"tr\":[160,173,8203,12288],\"zh-hans\":[160,173,8203,12288],\"zh-hant\":[173,12288]}');
1356
	}
1357

1358
	private static _data: Set<number> | undefined = undefined;
1359

1360
	private static getData() {
1361
		if (!this._data) {
1362
			this._data = new Set([...Object.values(InvisibleCharacters.getRawData())].flat());
1363
		}
1364
		return this._data;
1365
	}
1366

1367
	public static isInvisibleCharacter(codePoint: number): boolean {
1368
		return InvisibleCharacters.getData().has(codePoint);
1369
	}
1370

1371
	public static containsInvisibleCharacter(str: string): boolean {
1372
		for (let i = 0; i < str.length; i++) {
1373
			const codePoint = str.codePointAt(i);
1374
			if (typeof codePoint === 'number' && (InvisibleCharacters.isInvisibleCharacter(codePoint) || codePoint === CodePoint.space)) {
1375
				return true;
1376
			}
1377
		}
1378
		return false;
1379
	}
1380

1381
	public static get codePoints(): ReadonlySet<number> {
1382
		return InvisibleCharacters.getData();
1383
	}
1384
}
1385

1386
export const Ellipsis = '\u2026';
1387

1388
/**
1389
 * Convert a Unicode string to a string in which each 16-bit unit occupies only one byte
1390
 *
1391
 * From https://developer.mozilla.org/en-US/docs/Web/API/WindowOrWorkerGlobalScope/btoa
1392
 */
1393
function toBinary(str: string): string {
1394
	const codeUnits = new Uint16Array(str.length);
1395
	for (let i = 0; i < codeUnits.length; i++) {
1396
		codeUnits[i] = str.charCodeAt(i);
1397
	}
1398
	let binary = '';
1399
	const uint8array = new Uint8Array(codeUnits.buffer);
1400
	for (let i = 0; i < uint8array.length; i++) {
1401
		binary += String.fromCharCode(uint8array[i]);
1402
	}
1403
	return binary;
1404
}
1405

1406
/**
1407
 * Version of the global `btoa` function that handles multi-byte characters instead
1408
 * of throwing an exception.
1409
 */
1410

1411
export function multibyteAwareBtoa(str: string): string {
1412
	return btoa(toBinary(str));
1413
}
1414

1415
Product

Resources

Company
