1/* @internal */ // Don't expose that we use this
2// Based on lib.es6.d.ts
3interface PromiseConstructor {
4    new <T>(executor: (resolve: (value?: T | PromiseLike<T>) => void, reject: (reason?: any) => void) => void): Promise<T>;
5    reject(reason: any): Promise<never>;
6    all<T>(values: (T | PromiseLike<T>)[]): Promise<T[]>;
7}
8/* @internal */
9declare var Promise: PromiseConstructor; // eslint-disable-line no-var
10
11/* @internal */
12namespace ts {
13    // These utilities are common to multiple language service features.
14    //#region
15    export const scanner: Scanner = createScanner(ScriptTarget.Latest, /*skipTrivia*/ true);
16
17    export const enum SemanticMeaning {
18        None = 0x0,
19        Value = 0x1,
20        Type = 0x2,
21        Namespace = 0x4,
22        All = Value | Type | Namespace
23    }
24
25    export function getMeaningFromDeclaration(node: Node): SemanticMeaning {
26        switch (node.kind) {
27            case SyntaxKind.VariableDeclaration:
28                return isInJSFile(node) && getJSDocEnumTag(node) ? SemanticMeaning.All : SemanticMeaning.Value;
29
30            case SyntaxKind.Parameter:
31            case SyntaxKind.BindingElement:
32            case SyntaxKind.PropertyDeclaration:
33            case SyntaxKind.PropertySignature:
34            case SyntaxKind.PropertyAssignment:
35            case SyntaxKind.ShorthandPropertyAssignment:
36            case SyntaxKind.MethodDeclaration:
37            case SyntaxKind.MethodSignature:
38            case SyntaxKind.Constructor:
39            case SyntaxKind.GetAccessor:
40            case SyntaxKind.SetAccessor:
41            case SyntaxKind.FunctionDeclaration:
42            case SyntaxKind.FunctionExpression:
43            case SyntaxKind.ArrowFunction:
44            case SyntaxKind.CatchClause:
45            case SyntaxKind.JsxAttribute:
46                return SemanticMeaning.Value;
47
48            case SyntaxKind.TypeParameter:
49            case SyntaxKind.InterfaceDeclaration:
50            case SyntaxKind.TypeAliasDeclaration:
51            case SyntaxKind.TypeLiteral:
52                return SemanticMeaning.Type;
53
54            case SyntaxKind.JSDocTypedefTag:
55                // If it has no name node, it shares the name with the value declaration below it.
56                return (node as JSDocTypedefTag).name === undefined ? SemanticMeaning.Value | SemanticMeaning.Type : SemanticMeaning.Type;
57
58            case SyntaxKind.EnumMember:
59            case SyntaxKind.ClassDeclaration:
60            case SyntaxKind.StructDeclaration:
61                return SemanticMeaning.Value | SemanticMeaning.Type;
62            case SyntaxKind.AnnotationDeclaration:
63                return SemanticMeaning.Type;
64
65            case SyntaxKind.ModuleDeclaration:
66                if (isAmbientModule(node as ModuleDeclaration)) {
67                    return SemanticMeaning.Namespace | SemanticMeaning.Value;
68                }
69                else if (getModuleInstanceState(node as ModuleDeclaration) === ModuleInstanceState.Instantiated) {
70                    return SemanticMeaning.Namespace | SemanticMeaning.Value;
71                }
72                else {
73                    return SemanticMeaning.Namespace;
74                }
75
76            case SyntaxKind.EnumDeclaration:
77            case SyntaxKind.NamedImports:
78            case SyntaxKind.ImportSpecifier:
79            case SyntaxKind.ImportEqualsDeclaration:
80            case SyntaxKind.ImportDeclaration:
81            case SyntaxKind.ExportAssignment:
82            case SyntaxKind.ExportDeclaration:
83                return SemanticMeaning.All;
84
85            // An external module can be a Value
86            case SyntaxKind.SourceFile:
87                return SemanticMeaning.Namespace | SemanticMeaning.Value;
88        }
89
90        return SemanticMeaning.All;
91    }
92
93    export function getMeaningFromLocation(node: Node): SemanticMeaning {
94        node = getAdjustedReferenceLocation(node);
95        const parent = node.parent;
96        if (node.kind === SyntaxKind.SourceFile) {
97            return SemanticMeaning.Value;
98        }
99        else if (isExportAssignment(parent)
100            || isExportSpecifier(parent)
101            || isExternalModuleReference(parent)
102            || isImportSpecifier(parent)
103            || isImportClause(parent)
104            || isImportEqualsDeclaration(parent) && node === parent.name) {
105            return SemanticMeaning.All;
106        }
107        else if (isInRightSideOfInternalImportEqualsDeclaration(node)) {
108            return getMeaningFromRightHandSideOfImportEquals(node as Identifier);
109        }
110        else if (isDeclarationName(node)) {
111            return getMeaningFromDeclaration(parent);
112        }
113        else if (isEntityName(node) && findAncestor(node, or(isJSDocNameReference, isJSDocLinkLike, isJSDocMemberName))) {
114            return SemanticMeaning.All;
115        }
116        else if (isTypeReference(node)) {
117            return SemanticMeaning.Type;
118        }
119        else if (isNamespaceReference(node)) {
120            return SemanticMeaning.Namespace;
121        }
122        else if (isTypeParameterDeclaration(parent)) {
123            Debug.assert(isJSDocTemplateTag(parent.parent)); // Else would be handled by isDeclarationName
124            return SemanticMeaning.Type;
125        }
126        else if (isLiteralTypeNode(parent)) {
127            // This might be T["name"], which is actually referencing a property and not a type. So allow both meanings.
128            return SemanticMeaning.Type | SemanticMeaning.Value;
129        }
130        else {
131            return SemanticMeaning.Value;
132        }
133    }
134
135    function getMeaningFromRightHandSideOfImportEquals(node: Node): SemanticMeaning {
136        //     import a = |b|; // Namespace
137        //     import a = |b.c|; // Value, type, namespace
138        //     import a = |b.c|.d; // Namespace
139        const name = node.kind === SyntaxKind.QualifiedName ? node : isQualifiedName(node.parent) && node.parent.right === node ? node.parent : undefined;
140        return name && name.parent.kind === SyntaxKind.ImportEqualsDeclaration ? SemanticMeaning.All : SemanticMeaning.Namespace;
141    }
142
143    export function isInRightSideOfInternalImportEqualsDeclaration(node: Node) {
144        while (node.parent.kind === SyntaxKind.QualifiedName) {
145            node = node.parent;
146        }
147        return isInternalModuleImportEqualsDeclaration(node.parent) && node.parent.moduleReference === node;
148    }
149
150    function isNamespaceReference(node: Node): boolean {
151        return isQualifiedNameNamespaceReference(node) || isPropertyAccessNamespaceReference(node);
152    }
153
154    function isQualifiedNameNamespaceReference(node: Node): boolean {
155        let root = node;
156        let isLastClause = true;
157        if (root.parent.kind === SyntaxKind.QualifiedName) {
158            while (root.parent && root.parent.kind === SyntaxKind.QualifiedName) {
159                root = root.parent;
160            }
161
162            isLastClause = (root as QualifiedName).right === node;
163        }
164
165        return root.parent.kind === SyntaxKind.TypeReference && !isLastClause;
166    }
167
168    function isPropertyAccessNamespaceReference(node: Node): boolean {
169        let root = node;
170        let isLastClause = true;
171        if (root.parent.kind === SyntaxKind.PropertyAccessExpression) {
172            while (root.parent && root.parent.kind === SyntaxKind.PropertyAccessExpression) {
173                root = root.parent;
174            }
175
176            isLastClause = (root as PropertyAccessExpression).name === node;
177        }
178
179        if (!isLastClause && root.parent.kind === SyntaxKind.ExpressionWithTypeArguments && root.parent.parent.kind === SyntaxKind.HeritageClause) {
180            const decl = root.parent.parent.parent;
181            return ((decl.kind === SyntaxKind.ClassDeclaration || decl.kind === SyntaxKind.StructDeclaration) && (root.parent.parent as HeritageClause).token === SyntaxKind.ImplementsKeyword) ||
182                (decl.kind === SyntaxKind.InterfaceDeclaration && (root.parent.parent as HeritageClause).token === SyntaxKind.ExtendsKeyword);
183        }
184
185        return false;
186    }
187
188    function isTypeReference(node: Node): boolean {
189        if (isRightSideOfQualifiedNameOrPropertyAccess(node)) {
190            node = node.parent;
191        }
192
193        switch (node.kind) {
194            case SyntaxKind.ThisKeyword:
195                return !isExpressionNode(node);
196            case SyntaxKind.ThisType:
197                return true;
198        }
199
200        switch (node.parent.kind) {
201            case SyntaxKind.TypeReference:
202                return true;
203            case SyntaxKind.ImportType:
204                return !(node.parent as ImportTypeNode).isTypeOf;
205            case SyntaxKind.ExpressionWithTypeArguments:
206                return isPartOfTypeNode(node.parent);
207        }
208
209        return false;
210    }
211
212    export function isCallExpressionTarget(node: Node, includeElementAccess = false, skipPastOuterExpressions = false): boolean {
213        return isCalleeWorker(node, isCallExpression, selectExpressionOfCallOrNewExpressionOrDecorator, includeElementAccess, skipPastOuterExpressions);
214    }
215
216    export function isNewExpressionTarget(node: Node, includeElementAccess = false, skipPastOuterExpressions = false): boolean {
217        return isCalleeWorker(node, isNewExpression, selectExpressionOfCallOrNewExpressionOrDecorator, includeElementAccess, skipPastOuterExpressions);
218    }
219
220    export function isCallOrNewExpressionTarget(node: Node, includeElementAccess = false, skipPastOuterExpressions = false): boolean {
221        return isCalleeWorker(node, isCallOrNewExpression, selectExpressionOfCallOrNewExpressionOrDecorator, includeElementAccess, skipPastOuterExpressions);
222    }
223
224    export function isTaggedTemplateTag(node: Node, includeElementAccess = false, skipPastOuterExpressions = false): boolean {
225        return isCalleeWorker(node, isTaggedTemplateExpression, selectTagOfTaggedTemplateExpression, includeElementAccess, skipPastOuterExpressions);
226    }
227
228    export function isDecoratorTarget(node: Node, includeElementAccess = false, skipPastOuterExpressions = false): boolean {
229        return isCalleeWorker(node, isDecorator, selectExpressionOfCallOrNewExpressionOrDecorator, includeElementAccess, skipPastOuterExpressions);
230    }
231
232    export function isJsxOpeningLikeElementTagName(node: Node, includeElementAccess = false, skipPastOuterExpressions = false): boolean {
233        return isCalleeWorker(node, isJsxOpeningLikeElement, selectTagNameOfJsxOpeningLikeElement, includeElementAccess, skipPastOuterExpressions);
234    }
235
236    function selectExpressionOfCallOrNewExpressionOrDecorator(node: CallExpression | NewExpression | Decorator) {
237        return node.expression;
238    }
239
240    function selectTagOfTaggedTemplateExpression(node: TaggedTemplateExpression) {
241        return node.tag;
242    }
243
244    function selectTagNameOfJsxOpeningLikeElement(node: JsxOpeningLikeElement) {
245        return node.tagName;
246    }
247
248    function isCalleeWorker<T extends CallExpression | NewExpression | TaggedTemplateExpression | Decorator | JsxOpeningLikeElement>(node: Node, pred: (node: Node) => node is T, calleeSelector: (node: T) => Expression, includeElementAccess: boolean, skipPastOuterExpressions: boolean) {
249        let target = includeElementAccess ? climbPastPropertyOrElementAccess(node) : climbPastPropertyAccess(node);
250        if (skipPastOuterExpressions) {
251            target = skipOuterExpressions(target);
252        }
253        return !!target && !!target.parent && pred(target.parent) && calleeSelector(target.parent) === target;
254    }
255
256    export function climbPastPropertyAccess(node: Node) {
257        return isRightSideOfPropertyAccess(node) ? node.parent : node;
258    }
259
260    export function climbPastPropertyOrElementAccess(node: Node) {
261        return isRightSideOfPropertyAccess(node) || isArgumentExpressionOfElementAccess(node) ? node.parent : node;
262    }
263
264    export function getTargetLabel(referenceNode: Node, labelName: string): Identifier | undefined {
265        while (referenceNode) {
266            if (referenceNode.kind === SyntaxKind.LabeledStatement && (referenceNode as LabeledStatement).label.escapedText === labelName) {
267                return (referenceNode as LabeledStatement).label;
268            }
269            referenceNode = referenceNode.parent;
270        }
271        return undefined;
272    }
273
274    export function hasPropertyAccessExpressionWithName(node: CallExpression, funcName: string): boolean {
275        if (!isPropertyAccessExpression(node.expression)) {
276            return false;
277        }
278
279        return node.expression.name.text === funcName;
280    }
281
282    export function isJumpStatementTarget(node: Node): node is Identifier & { parent: BreakOrContinueStatement } {
283        return isIdentifier(node) && tryCast(node.parent, isBreakOrContinueStatement)?.label === node;
284    }
285
286    export function isLabelOfLabeledStatement(node: Node): node is Identifier {
287        return isIdentifier(node) && tryCast(node.parent, isLabeledStatement)?.label === node;
288    }
289
290    export function isLabelName(node: Node): boolean {
291        return isLabelOfLabeledStatement(node) || isJumpStatementTarget(node);
292    }
293
294    export function isTagName(node: Node): boolean {
295        return tryCast(node.parent, isJSDocTag)?.tagName === node;
296    }
297
298    export function isRightSideOfQualifiedName(node: Node) {
299        return tryCast(node.parent, isQualifiedName)?.right === node;
300    }
301
302    export function isRightSideOfPropertyAccess(node: Node) {
303        return tryCast(node.parent, isPropertyAccessExpression)?.name === node;
304    }
305
306    export function isArgumentExpressionOfElementAccess(node: Node) {
307        return tryCast(node.parent, isElementAccessExpression)?.argumentExpression === node;
308    }
309
310    export function isNameOfModuleDeclaration(node: Node) {
311        return tryCast(node.parent, isModuleDeclaration)?.name === node;
312    }
313
314    export function isNameOfFunctionDeclaration(node: Node): boolean {
315        return isIdentifier(node) && tryCast(node.parent, isFunctionLike)?.name === node;
316    }
317
318    export function isLiteralNameOfPropertyDeclarationOrIndexAccess(node: StringLiteral | NumericLiteral | NoSubstitutionTemplateLiteral): boolean {
319        switch (node.parent.kind) {
320            case SyntaxKind.PropertyDeclaration:
321            case SyntaxKind.PropertySignature:
322            case SyntaxKind.PropertyAssignment:
323            case SyntaxKind.EnumMember:
324            case SyntaxKind.MethodDeclaration:
325            case SyntaxKind.MethodSignature:
326            case SyntaxKind.GetAccessor:
327            case SyntaxKind.SetAccessor:
328            case SyntaxKind.ModuleDeclaration:
329                return getNameOfDeclaration(node.parent as Declaration) === node;
330            case SyntaxKind.ElementAccessExpression:
331                return (node.parent as ElementAccessExpression).argumentExpression === node;
332            case SyntaxKind.ComputedPropertyName:
333                return true;
334            case SyntaxKind.LiteralType:
335                return node.parent.parent.kind === SyntaxKind.IndexedAccessType;
336            default:
337                return false;
338        }
339    }
340
341    export function isExpressionOfExternalModuleImportEqualsDeclaration(node: Node) {
342        return isExternalModuleImportEqualsDeclaration(node.parent.parent) &&
343            getExternalModuleImportEqualsDeclarationExpression(node.parent.parent) === node;
344    }
345
346    export function getContainerNode(node: Node): Declaration | undefined {
347        if (isJSDocTypeAlias(node)) {
348            // This doesn't just apply to the node immediately under the comment, but to everything in its parent's scope.
349            // node.parent = the JSDoc comment, node.parent.parent = the node having the comment.
350            // Then we get parent again in the loop.
351            node = node.parent.parent;
352        }
353
354        while (true) {
355            node = node.parent;
356            if (!node) {
357                return undefined;
358            }
359            switch (node.kind) {
360                case SyntaxKind.SourceFile:
361                case SyntaxKind.MethodDeclaration:
362                case SyntaxKind.MethodSignature:
363                case SyntaxKind.FunctionDeclaration:
364                case SyntaxKind.FunctionExpression:
365                case SyntaxKind.GetAccessor:
366                case SyntaxKind.SetAccessor:
367                case SyntaxKind.ClassDeclaration:
368                case SyntaxKind.StructDeclaration:
369                case SyntaxKind.InterfaceDeclaration:
370                case SyntaxKind.EnumDeclaration:
371                case SyntaxKind.ModuleDeclaration:
372                    return node as Declaration;
373            }
374        }
375    }
376
377    export function getNodeKind(node: Node): ScriptElementKind {
378        switch (node.kind) {
379            case SyntaxKind.SourceFile:
380                return isExternalModule(node as SourceFile) ? ScriptElementKind.moduleElement : ScriptElementKind.scriptElement;
381            case SyntaxKind.ModuleDeclaration:
382                return ScriptElementKind.moduleElement;
383            case SyntaxKind.ClassDeclaration:
384            case SyntaxKind.ClassExpression:
385                return ScriptElementKind.classElement;
386            case SyntaxKind.StructDeclaration:
387                return ScriptElementKind.structElement;
388            case SyntaxKind.InterfaceDeclaration: return ScriptElementKind.interfaceElement;
389            case SyntaxKind.TypeAliasDeclaration:
390            case SyntaxKind.JSDocCallbackTag:
391            case SyntaxKind.JSDocTypedefTag:
392                return ScriptElementKind.typeElement;
393            case SyntaxKind.EnumDeclaration: return ScriptElementKind.enumElement;
394            case SyntaxKind.VariableDeclaration:
395                return getKindOfVariableDeclaration(node as VariableDeclaration);
396            case SyntaxKind.BindingElement:
397                return getKindOfVariableDeclaration(getRootDeclaration(node) as VariableDeclaration);
398            case SyntaxKind.ArrowFunction:
399            case SyntaxKind.FunctionDeclaration:
400            case SyntaxKind.FunctionExpression:
401                return ScriptElementKind.functionElement;
402            case SyntaxKind.GetAccessor: return ScriptElementKind.memberGetAccessorElement;
403            case SyntaxKind.SetAccessor: return ScriptElementKind.memberSetAccessorElement;
404            case SyntaxKind.MethodDeclaration:
405            case SyntaxKind.MethodSignature:
406                return ScriptElementKind.memberFunctionElement;
407            case SyntaxKind.PropertyAssignment:
408                const { initializer } = node as PropertyAssignment;
409                return isFunctionLike(initializer) ? ScriptElementKind.memberFunctionElement : ScriptElementKind.memberVariableElement;
410            case SyntaxKind.PropertyDeclaration:
411            case SyntaxKind.PropertySignature:
412            case SyntaxKind.ShorthandPropertyAssignment:
413            case SyntaxKind.SpreadAssignment:
414                return ScriptElementKind.memberVariableElement;
415            case SyntaxKind.IndexSignature: return ScriptElementKind.indexSignatureElement;
416            case SyntaxKind.ConstructSignature: return ScriptElementKind.constructSignatureElement;
417            case SyntaxKind.CallSignature: return ScriptElementKind.callSignatureElement;
418            case SyntaxKind.Constructor:
419            case SyntaxKind.ClassStaticBlockDeclaration:
420                return ScriptElementKind.constructorImplementationElement;
421            case SyntaxKind.TypeParameter: return ScriptElementKind.typeParameterElement;
422            case SyntaxKind.EnumMember: return ScriptElementKind.enumMemberElement;
423            case SyntaxKind.Parameter: return hasSyntacticModifier(node, ModifierFlags.ParameterPropertyModifier) ? ScriptElementKind.memberVariableElement : ScriptElementKind.parameterElement;
424            case SyntaxKind.ImportEqualsDeclaration:
425            case SyntaxKind.ImportSpecifier:
426            case SyntaxKind.ExportSpecifier:
427            case SyntaxKind.NamespaceImport:
428            case SyntaxKind.NamespaceExport:
429                return ScriptElementKind.alias;
430            case SyntaxKind.BinaryExpression:
431                const kind = getAssignmentDeclarationKind(node as BinaryExpression);
432                const { right } = node as BinaryExpression;
433                switch (kind) {
434                    case AssignmentDeclarationKind.ObjectDefinePropertyValue:
435                    case AssignmentDeclarationKind.ObjectDefinePropertyExports:
436                    case AssignmentDeclarationKind.ObjectDefinePrototypeProperty:
437                    case AssignmentDeclarationKind.None:
438                        return ScriptElementKind.unknown;
439                    case AssignmentDeclarationKind.ExportsProperty:
440                    case AssignmentDeclarationKind.ModuleExports:
441                        const rightKind = getNodeKind(right);
442                        return rightKind === ScriptElementKind.unknown ? ScriptElementKind.constElement : rightKind;
443                    case AssignmentDeclarationKind.PrototypeProperty:
444                        return isFunctionExpression(right) ? ScriptElementKind.memberFunctionElement : ScriptElementKind.memberVariableElement;
445                    case AssignmentDeclarationKind.ThisProperty:
446                        return ScriptElementKind.memberVariableElement; // property
447                    case AssignmentDeclarationKind.Property:
448                        // static method / property
449                        return isFunctionExpression(right) ? ScriptElementKind.memberFunctionElement : ScriptElementKind.memberVariableElement;
450                    case AssignmentDeclarationKind.Prototype:
451                        return ScriptElementKind.localClassElement;
452                    default: {
453                        assertType<never>(kind);
454                        return ScriptElementKind.unknown;
455                    }
456                }
457            case SyntaxKind.Identifier:
458                return isImportClause(node.parent) ? ScriptElementKind.alias : ScriptElementKind.unknown;
459            case SyntaxKind.ExportAssignment:
460                const scriptKind = getNodeKind((node as ExportAssignment).expression);
461                // If the expression didn't come back with something (like it does for an identifiers)
462                return scriptKind === ScriptElementKind.unknown ? ScriptElementKind.constElement : scriptKind;
463            default:
464                return ScriptElementKind.unknown;
465        }
466
467        function getKindOfVariableDeclaration(v: VariableDeclaration): ScriptElementKind {
468            return isVarConst(v)
469                ? ScriptElementKind.constElement
470                : isLet(v)
471                    ? ScriptElementKind.letElement
472                    : ScriptElementKind.variableElement;
473        }
474    }
475
476    export function isThis(node: Node): boolean {
477        switch (node.kind) {
478            case SyntaxKind.ThisKeyword:
479                // case SyntaxKind.ThisType: TODO: GH#9267
480                return true;
481            case SyntaxKind.Identifier:
482                // 'this' as a parameter
483                return identifierIsThisKeyword(node as Identifier) && node.parent.kind === SyntaxKind.Parameter;
484            default:
485                return false;
486        }
487    }
488
489    // Matches the beginning of a triple slash directive
490    const tripleSlashDirectivePrefixRegex = /^\/\/\/\s*</;
491
492    export interface ListItemInfo {
493        listItemIndex: number;
494        list: Node;
495    }
496
497    export function getLineStartPositionForPosition(position: number, sourceFile: SourceFileLike): number {
498        const lineStarts = getLineStarts(sourceFile);
499        const line = sourceFile.getLineAndCharacterOfPosition(position).line;
500        return lineStarts[line];
501    }
502
503    export function rangeContainsRange(r1: TextRange, r2: TextRange): boolean {
504        return startEndContainsRange(r1.pos, r1.end, r2);
505    }
506
507    export function rangeContainsRangeExclusive(r1: TextRange, r2: TextRange): boolean {
508        return rangeContainsPositionExclusive(r1, r2.pos) && rangeContainsPositionExclusive(r1, r2.end);
509    }
510
511    export function rangeContainsPosition(r: TextRange, pos: number): boolean {
512        return r.pos <= pos && pos <= r.end;
513    }
514
515    export function rangeContainsPositionExclusive(r: TextRange, pos: number) {
516        return r.pos < pos && pos < r.end;
517    }
518
519    export function startEndContainsRange(start: number, end: number, range: TextRange): boolean {
520        return start <= range.pos && end >= range.end;
521    }
522
523    export function rangeContainsStartEnd(range: TextRange, start: number, end: number): boolean {
524        return range.pos <= start && range.end >= end;
525    }
526
527    export function rangeOverlapsWithStartEnd(r1: TextRange, start: number, end: number) {
528        return startEndOverlapsWithStartEnd(r1.pos, r1.end, start, end);
529    }
530
531    export function nodeOverlapsWithStartEnd(node: Node, sourceFile: SourceFile, start: number, end: number) {
532        return startEndOverlapsWithStartEnd(node.getStart(sourceFile), node.end, start, end);
533    }
534
535    export function startEndOverlapsWithStartEnd(start1: number, end1: number, start2: number, end2: number) {
536        const start = Math.max(start1, start2);
537        const end = Math.min(end1, end2);
538        return start < end;
539    }
540
541    /**
542     * Assumes `candidate.start <= position` holds.
543     */
544    export function positionBelongsToNode(candidate: Node, position: number, sourceFile: SourceFile): boolean {
545        Debug.assert(candidate.pos <= position);
546        return position < candidate.end || !isCompletedNode(candidate, sourceFile);
547    }
548
549    function isCompletedNode(n: Node | undefined, sourceFile: SourceFile): boolean {
550        if (n === undefined || nodeIsMissing(n)) {
551            return false;
552        }
553
554        switch (n.kind) {
555            case SyntaxKind.ClassDeclaration:
556            case SyntaxKind.StructDeclaration:
557            case SyntaxKind.InterfaceDeclaration:
558            case SyntaxKind.EnumDeclaration:
559            case SyntaxKind.ObjectLiteralExpression:
560            case SyntaxKind.ObjectBindingPattern:
561            case SyntaxKind.TypeLiteral:
562            case SyntaxKind.Block:
563            case SyntaxKind.ModuleBlock:
564            case SyntaxKind.CaseBlock:
565            case SyntaxKind.NamedImports:
566            case SyntaxKind.NamedExports:
567                return nodeEndsWith(n, SyntaxKind.CloseBraceToken, sourceFile);
568            case SyntaxKind.CatchClause:
569                return isCompletedNode((n as CatchClause).block, sourceFile);
570            case SyntaxKind.NewExpression:
571                if (!(n as NewExpression).arguments) {
572                    return true;
573                }
574            // falls through
575
576            case SyntaxKind.CallExpression:
577            case SyntaxKind.ParenthesizedExpression:
578            case SyntaxKind.ParenthesizedType:
579                return nodeEndsWith(n, SyntaxKind.CloseParenToken, sourceFile);
580
581            case SyntaxKind.FunctionType:
582            case SyntaxKind.ConstructorType:
583                return isCompletedNode((n as SignatureDeclaration).type, sourceFile);
584
585            case SyntaxKind.Constructor:
586            case SyntaxKind.GetAccessor:
587            case SyntaxKind.SetAccessor:
588            case SyntaxKind.FunctionDeclaration:
589            case SyntaxKind.FunctionExpression:
590            case SyntaxKind.MethodDeclaration:
591            case SyntaxKind.MethodSignature:
592            case SyntaxKind.ConstructSignature:
593            case SyntaxKind.CallSignature:
594            case SyntaxKind.ArrowFunction:
595                if ((n as FunctionLikeDeclaration).body) {
596                    return isCompletedNode((n as FunctionLikeDeclaration).body, sourceFile);
597                }
598
599                if ((n as FunctionLikeDeclaration).type) {
600                    return isCompletedNode((n as FunctionLikeDeclaration).type, sourceFile);
601                }
602
603                // Even though type parameters can be unclosed, we can get away with
604                // having at least a closing paren.
605                return hasChildOfKind(n, SyntaxKind.CloseParenToken, sourceFile);
606
607            case SyntaxKind.ModuleDeclaration:
608                return !!(n as ModuleDeclaration).body && isCompletedNode((n as ModuleDeclaration).body, sourceFile);
609
610            case SyntaxKind.IfStatement:
611                if ((n as IfStatement).elseStatement) {
612                    return isCompletedNode((n as IfStatement).elseStatement, sourceFile);
613                }
614                return isCompletedNode((n as IfStatement).thenStatement, sourceFile);
615
616            case SyntaxKind.ExpressionStatement:
617                return isCompletedNode((n as ExpressionStatement).expression, sourceFile) ||
618                    hasChildOfKind(n, SyntaxKind.SemicolonToken, sourceFile);
619
620            case SyntaxKind.ArrayLiteralExpression:
621            case SyntaxKind.ArrayBindingPattern:
622            case SyntaxKind.ElementAccessExpression:
623            case SyntaxKind.ComputedPropertyName:
624            case SyntaxKind.TupleType:
625                return nodeEndsWith(n, SyntaxKind.CloseBracketToken, sourceFile);
626
627            case SyntaxKind.IndexSignature:
628                if ((n as IndexSignatureDeclaration).type) {
629                    return isCompletedNode((n as IndexSignatureDeclaration).type, sourceFile);
630                }
631
632                return hasChildOfKind(n, SyntaxKind.CloseBracketToken, sourceFile);
633
634            case SyntaxKind.CaseClause:
635            case SyntaxKind.DefaultClause:
636                // there is no such thing as terminator token for CaseClause/DefaultClause so for simplicity always consider them non-completed
637                return false;
638
639            case SyntaxKind.ForStatement:
640            case SyntaxKind.ForInStatement:
641            case SyntaxKind.ForOfStatement:
642            case SyntaxKind.WhileStatement:
643                return isCompletedNode((n as IterationStatement).statement, sourceFile);
644            case SyntaxKind.DoStatement:
645                // rough approximation: if DoStatement has While keyword - then if node is completed is checking the presence of ')';
646                return hasChildOfKind(n, SyntaxKind.WhileKeyword, sourceFile)
647                    ? nodeEndsWith(n, SyntaxKind.CloseParenToken, sourceFile)
648                    : isCompletedNode((n as DoStatement).statement, sourceFile);
649
650            case SyntaxKind.TypeQuery:
651                return isCompletedNode((n as TypeQueryNode).exprName, sourceFile);
652
653            case SyntaxKind.TypeOfExpression:
654            case SyntaxKind.DeleteExpression:
655            case SyntaxKind.VoidExpression:
656            case SyntaxKind.YieldExpression:
657            case SyntaxKind.SpreadElement:
658                const unaryWordExpression = n as (TypeOfExpression | DeleteExpression | VoidExpression | YieldExpression | SpreadElement);
659                return isCompletedNode(unaryWordExpression.expression, sourceFile);
660
661            case SyntaxKind.TaggedTemplateExpression:
662                return isCompletedNode((n as TaggedTemplateExpression).template, sourceFile);
663            case SyntaxKind.TemplateExpression:
664                const lastSpan = lastOrUndefined((n as TemplateExpression).templateSpans);
665                return isCompletedNode(lastSpan, sourceFile);
666            case SyntaxKind.TemplateSpan:
667                return nodeIsPresent((n as TemplateSpan).literal);
668
669            case SyntaxKind.ExportDeclaration:
670            case SyntaxKind.ImportDeclaration:
671                return nodeIsPresent((n as ExportDeclaration | ImportDeclaration).moduleSpecifier);
672
673            case SyntaxKind.PrefixUnaryExpression:
674                return isCompletedNode((n as PrefixUnaryExpression).operand, sourceFile);
675            case SyntaxKind.BinaryExpression:
676                return isCompletedNode((n as BinaryExpression).right, sourceFile);
677            case SyntaxKind.ConditionalExpression:
678                return isCompletedNode((n as ConditionalExpression).whenFalse, sourceFile);
679
680            default:
681                return true;
682        }
683    }
684
685    /*
686     * Checks if node ends with 'expectedLastToken'.
687     * If child at position 'length - 1' is 'SemicolonToken' it is skipped and 'expectedLastToken' is compared with child at position 'length - 2'.
688     */
689    function nodeEndsWith(n: Node, expectedLastToken: SyntaxKind, sourceFile: SourceFile): boolean {
690        const children = n.getChildren(sourceFile);
691        if (children.length) {
692            const lastChild = last(children);
693            if (lastChild.kind === expectedLastToken) {
694                return true;
695            }
696            else if (lastChild.kind === SyntaxKind.SemicolonToken && children.length !== 1) {
697                return children[children.length - 2].kind === expectedLastToken;
698            }
699        }
700        return false;
701    }
702
703    export function findListItemInfo(node: Node): ListItemInfo | undefined {
704        const list = findContainingList(node);
705
706        // It is possible at this point for syntaxList to be undefined, either if
707        // node.parent had no list child, or if none of its list children contained
708        // the span of node. If this happens, return undefined. The caller should
709        // handle this case.
710        if (!list) {
711            return undefined;
712        }
713
714        const children = list.getChildren();
715        const listItemIndex = indexOfNode(children, node);
716
717        return {
718            listItemIndex,
719            list
720        };
721    }
722
723    export function hasChildOfKind(n: Node, kind: SyntaxKind, sourceFile: SourceFile): boolean {
724        return !!findChildOfKind(n, kind, sourceFile);
725    }
726
727    export function findChildOfKind<T extends Node>(n: Node, kind: T["kind"], sourceFile: SourceFileLike): T | undefined {
728        return find(n.getChildren(sourceFile), (c): c is T => c.kind === kind);
729    }
730
731    export function findContainingList(node: Node): SyntaxList | undefined {
732        // The node might be a list element (nonsynthetic) or a comma (synthetic). Either way, it will
733        // be parented by the container of the SyntaxList, not the SyntaxList itself.
734        // In order to find the list item index, we first need to locate SyntaxList itself and then search
735        // for the position of the relevant node (or comma).
736        const syntaxList = find(node.parent.getChildren(), (c): c is SyntaxList => isSyntaxList(c) && rangeContainsRange(c, node));
737        // Either we didn't find an appropriate list, or the list must contain us.
738        Debug.assert(!syntaxList || contains(syntaxList.getChildren(), node));
739        return syntaxList;
740    }
741
742    function isDefaultModifier(node: Node) {
743        return node.kind === SyntaxKind.DefaultKeyword;
744    }
745
746    function isClassKeyword(node: Node) {
747        return node.kind === SyntaxKind.ClassKeyword;
748    }
749
750    function isFunctionKeyword(node: Node) {
751        return node.kind === SyntaxKind.FunctionKeyword;
752    }
753
754    function getAdjustedLocationForClass(node: ClassDeclaration | ClassExpression | StructDeclaration) {
755        if (isNamedDeclaration(node)) {
756            return node.name;
757        }
758        if (isClassDeclaration(node) || isStructDeclaration(node)) {
759            // for class and function declarations, use the `default` modifier
760            // when the declaration is unnamed.
761            const defaultModifier = node.modifiers && find(node.modifiers, isDefaultModifier);
762            if (defaultModifier) return defaultModifier;
763        }
764        if (isClassExpression(node)) {
765            // for class expressions, use the `class` keyword when the class is unnamed
766            const classKeyword = find(node.getChildren(), isClassKeyword);
767            if (classKeyword) return classKeyword;
768        }
769    }
770
771    function getAdjustedLocationForFunction(node: FunctionDeclaration | FunctionExpression) {
772        if (isNamedDeclaration(node)) {
773            return node.name;
774        }
775        if (isFunctionDeclaration(node)) {
776            // for class and function declarations, use the `default` modifier
777            // when the declaration is unnamed.
778            const defaultModifier = find(node.modifiers, isDefaultModifier);
779            if (defaultModifier) return defaultModifier;
780        }
781        if (isFunctionExpression(node)) {
782            // for function expressions, use the `function` keyword when the function is unnamed
783            const functionKeyword = find(node.getChildren(), isFunctionKeyword);
784            if (functionKeyword) return functionKeyword;
785        }
786    }
787
788    function getAncestorTypeNode(node: Node) {
789        let lastTypeNode: TypeNode | undefined;
790        findAncestor(node, a => {
791            if (isTypeNode(a)) {
792                lastTypeNode = a;
793            }
794            return !isQualifiedName(a.parent) && !isTypeNode(a.parent) && !isTypeElement(a.parent);
795        });
796        return lastTypeNode;
797    }
798
799    export function getContextualTypeFromParentOrAncestorTypeNode(node: Expression, checker: TypeChecker): Type | undefined {
800        if (node.flags & (NodeFlags.JSDoc & ~NodeFlags.JavaScriptFile)) return undefined;
801
802        const contextualType = getContextualTypeFromParent(node, checker);
803        if (contextualType) return contextualType;
804
805        const ancestorTypeNode = getAncestorTypeNode(node);
806        return ancestorTypeNode && checker.getTypeAtLocation(ancestorTypeNode);
807    }
808
809    function getAdjustedLocationForDeclaration(node: Node, forRename: boolean) {
810        if (!forRename) {
811            switch (node.kind) {
812                case SyntaxKind.ClassDeclaration:
813                case SyntaxKind.ClassExpression:
814                case SyntaxKind.StructDeclaration:
815                    return getAdjustedLocationForClass(node as ClassDeclaration | ClassExpression | StructDeclaration);
816                case SyntaxKind.FunctionDeclaration:
817                case SyntaxKind.FunctionExpression:
818                    return getAdjustedLocationForFunction(node as FunctionDeclaration | FunctionExpression);
819                case SyntaxKind.Constructor:
820                    return node;
821            }
822        }
823        if (isNamedDeclaration(node)) {
824            return node.name;
825        }
826    }
827
828    function getAdjustedLocationForImportDeclaration(node: ImportDeclaration, forRename: boolean) {
829        if (node.importClause) {
830            if (node.importClause.name && node.importClause.namedBindings) {
831                // do not adjust if we have both a name and named bindings
832                return;
833            }
834
835            // /**/import [|name|] from ...;
836            // import /**/type [|name|] from ...;
837            if (node.importClause.name) {
838                return node.importClause.name;
839            }
840
841            // /**/import { [|name|] } from ...;
842            // /**/import { propertyName as [|name|] } from ...;
843            // /**/import * as [|name|] from ...;
844            // import /**/type { [|name|] } from ...;
845            // import /**/type { propertyName as [|name|] } from ...;
846            // import /**/type * as [|name|] from ...;
847            if (node.importClause.namedBindings) {
848                if (isNamedImports(node.importClause.namedBindings)) {
849                    // do nothing if there is more than one binding
850                    const onlyBinding = singleOrUndefined(node.importClause.namedBindings.elements);
851                    if (!onlyBinding) {
852                        return;
853                    }
854                    return onlyBinding.name;
855                }
856                else if (isNamespaceImport(node.importClause.namedBindings)) {
857                    return node.importClause.namedBindings.name;
858                }
859            }
860        }
861        if (!forRename) {
862            // /**/import "[|module|]";
863            // /**/import ... from "[|module|]";
864            // import /**/type ... from "[|module|]";
865            return node.moduleSpecifier;
866        }
867    }
868
869    function getAdjustedLocationForExportDeclaration(node: ExportDeclaration, forRename: boolean) {
870        if (node.exportClause) {
871            // /**/export { [|name|] } ...
872            // /**/export { propertyName as [|name|] } ...
873            // /**/export * as [|name|] ...
874            // export /**/type { [|name|] } from ...
875            // export /**/type { propertyName as [|name|] } from ...
876            // export /**/type * as [|name|] ...
877            if (isNamedExports(node.exportClause)) {
878                // do nothing if there is more than one binding
879                const onlyBinding = singleOrUndefined(node.exportClause.elements);
880                if (!onlyBinding) {
881                    return;
882                }
883                return node.exportClause.elements[0].name;
884            }
885            else if (isNamespaceExport(node.exportClause)) {
886                return node.exportClause.name;
887            }
888        }
889        if (!forRename) {
890            // /**/export * from "[|module|]";
891            // export /**/type * from "[|module|]";
892            return node.moduleSpecifier;
893        }
894    }
895
896    function getAdjustedLocationForHeritageClause(node: HeritageClause) {
897        // /**/extends [|name|]
898        // /**/implements [|name|]
899        if (node.types.length === 1) {
900            return node.types[0].expression;
901        }
902
903        // /**/extends name1, name2 ...
904        // /**/implements name1, name2 ...
905    }
906
907    function getAdjustedLocation(node: Node, forRename: boolean): Node {
908        const { parent } = node;
909        // /**/<modifier> [|name|] ...
910        // /**/<modifier> <class|interface|type|enum|module|namespace|function|get|set> [|name|] ...
911        // /**/<class|interface|type|enum|module|namespace|function|get|set> [|name|] ...
912        // /**/import [|name|] = ...
913        //
914        // NOTE: If the node is a modifier, we don't adjust its location if it is the `default` modifier as that is handled
915        // specially by `getSymbolAtLocation`.
916        if (isModifier(node) && (forRename || node.kind !== SyntaxKind.DefaultKeyword) ? canHaveModifiers(parent) && contains(parent.modifiers, node) :
917            node.kind === SyntaxKind.ClassKeyword ? isClassDeclaration(parent) || isClassExpression(node) :
918                node.kind === SyntaxKind.FunctionKeyword ? isFunctionDeclaration(parent) || isFunctionExpression(node) :
919                    node.kind === SyntaxKind.InterfaceKeyword ? isInterfaceDeclaration(parent) :
920                        node.kind === SyntaxKind.EnumKeyword ? isEnumDeclaration(parent) :
921                            node.kind === SyntaxKind.TypeKeyword ? isTypeAliasDeclaration(parent) :
922                                node.kind === SyntaxKind.NamespaceKeyword || node.kind === SyntaxKind.ModuleKeyword ? isModuleDeclaration(parent) :
923                                    node.kind === SyntaxKind.ImportKeyword ? isImportEqualsDeclaration(parent) :
924                                        node.kind === SyntaxKind.GetKeyword ? isGetAccessorDeclaration(parent) :
925                                            node.kind === SyntaxKind.SetKeyword && isSetAccessorDeclaration(parent)) {
926            const location = getAdjustedLocationForDeclaration(parent, forRename);
927            if (location) {
928                return location;
929            }
930        }
931        // /**/<var|let|const> [|name|] ...
932        if ((node.kind === SyntaxKind.VarKeyword || node.kind === SyntaxKind.ConstKeyword || node.kind === SyntaxKind.LetKeyword) &&
933            isVariableDeclarationList(parent) && parent.declarations.length === 1) {
934            const decl = parent.declarations[0];
935            if (isIdentifier(decl.name)) {
936                return decl.name;
937            }
938        }
939        if (node.kind === SyntaxKind.TypeKeyword) {
940            // import /**/type [|name|] from ...;
941            // import /**/type { [|name|] } from ...;
942            // import /**/type { propertyName as [|name|] } from ...;
943            // import /**/type ... from "[|module|]";
944            if (isImportClause(parent) && parent.isTypeOnly) {
945                const location = getAdjustedLocationForImportDeclaration(parent.parent, forRename);
946                if (location) {
947                    return location;
948                }
949            }
950            // export /**/type { [|name|] } from ...;
951            // export /**/type { propertyName as [|name|] } from ...;
952            // export /**/type * from "[|module|]";
953            // export /**/type * as ... from "[|module|]";
954            if (isExportDeclaration(parent) && parent.isTypeOnly) {
955                const location = getAdjustedLocationForExportDeclaration(parent, forRename);
956                if (location) {
957                    return location;
958                }
959            }
960        }
961        // import { propertyName /**/as [|name|] } ...
962        // import * /**/as [|name|] ...
963        // export { propertyName /**/as [|name|] } ...
964        // export * /**/as [|name|] ...
965        if (node.kind === SyntaxKind.AsKeyword) {
966            if (isImportSpecifier(parent) && parent.propertyName ||
967                isExportSpecifier(parent) && parent.propertyName ||
968                isNamespaceImport(parent) ||
969                isNamespaceExport(parent)) {
970                return parent.name;
971            }
972            if (isExportDeclaration(parent) && parent.exportClause && isNamespaceExport(parent.exportClause)) {
973                return parent.exportClause.name;
974            }
975        }
976        // /**/import [|name|] from ...;
977        // /**/import { [|name|] } from ...;
978        // /**/import { propertyName as [|name|] } from ...;
979        // /**/import ... from "[|module|]";
980        // /**/import "[|module|]";
981        if (node.kind === SyntaxKind.ImportKeyword && isImportDeclaration(parent)) {
982            const location = getAdjustedLocationForImportDeclaration(parent, forRename);
983            if (location) {
984                return location;
985            }
986        }
987        if (node.kind === SyntaxKind.ExportKeyword) {
988            // /**/export { [|name|] } ...;
989            // /**/export { propertyName as [|name|] } ...;
990            // /**/export * from "[|module|]";
991            // /**/export * as ... from "[|module|]";
992            if (isExportDeclaration(parent)) {
993                const location = getAdjustedLocationForExportDeclaration(parent, forRename);
994                if (location) {
995                    return location;
996                }
997            }
998            // NOTE: We don't adjust the location of the `default` keyword as that is handled specially by `getSymbolAtLocation`.
999            // /**/export default [|name|];
1000            // /**/export = [|name|];
1001            if (isExportAssignment(parent)) {
1002                return skipOuterExpressions(parent.expression);
1003            }
1004        }
1005        // import name = /**/require("[|module|]");
1006        if (node.kind === SyntaxKind.RequireKeyword && isExternalModuleReference(parent)) {
1007            return parent.expression;
1008        }
1009        // import ... /**/from "[|module|]";
1010        // export ... /**/from "[|module|]";
1011        if (node.kind === SyntaxKind.FromKeyword && (isImportDeclaration(parent) || isExportDeclaration(parent)) && parent.moduleSpecifier) {
1012            return parent.moduleSpecifier;
1013        }
1014        // class ... /**/extends [|name|] ...
1015        // class ... /**/implements [|name|] ...
1016        // class ... /**/implements name1, name2 ...
1017        // interface ... /**/extends [|name|] ...
1018        // interface ... /**/extends name1, name2 ...
1019        if ((node.kind === SyntaxKind.ExtendsKeyword || node.kind === SyntaxKind.ImplementsKeyword) && isHeritageClause(parent) && parent.token === node.kind) {
1020            const location = getAdjustedLocationForHeritageClause(parent);
1021            if (location) {
1022                return location;
1023            }
1024        }
1025        if (node.kind === SyntaxKind.ExtendsKeyword) {
1026            // ... <T /**/extends [|U|]> ...
1027            if (isTypeParameterDeclaration(parent) && parent.constraint && isTypeReferenceNode(parent.constraint)) {
1028                return parent.constraint.typeName;
1029            }
1030            // ... T /**/extends [|U|] ? ...
1031            if (isConditionalTypeNode(parent) && isTypeReferenceNode(parent.extendsType)) {
1032                return parent.extendsType.typeName;
1033            }
1034        }
1035        // ... T extends /**/infer [|U|] ? ...
1036        if (node.kind === SyntaxKind.InferKeyword && isInferTypeNode(parent)) {
1037            return parent.typeParameter.name;
1038        }
1039        // { [ [|K|] /**/in keyof T]: ... }
1040        if (node.kind === SyntaxKind.InKeyword && isTypeParameterDeclaration(parent) && isMappedTypeNode(parent.parent)) {
1041            return parent.name;
1042        }
1043        // /**/keyof [|T|]
1044        if (node.kind === SyntaxKind.KeyOfKeyword && isTypeOperatorNode(parent) && parent.operator === SyntaxKind.KeyOfKeyword &&
1045            isTypeReferenceNode(parent.type)) {
1046            return parent.type.typeName;
1047        }
1048        // /**/readonly [|name|][]
1049        if (node.kind === SyntaxKind.ReadonlyKeyword && isTypeOperatorNode(parent) && parent.operator === SyntaxKind.ReadonlyKeyword &&
1050            isArrayTypeNode(parent.type) && isTypeReferenceNode(parent.type.elementType)) {
1051            return parent.type.elementType.typeName;
1052        }
1053        if (!forRename) {
1054            // /**/new [|name|]
1055            // /**/void [|name|]
1056            // /**/void obj.[|name|]
1057            // /**/typeof [|name|]
1058            // /**/typeof obj.[|name|]
1059            // /**/await [|name|]
1060            // /**/await obj.[|name|]
1061            // /**/yield [|name|]
1062            // /**/yield obj.[|name|]
1063            // /**/delete obj.[|name|]
1064            if (node.kind === SyntaxKind.NewKeyword && isNewExpression(parent) ||
1065                node.kind === SyntaxKind.VoidKeyword && isVoidExpression(parent) ||
1066                node.kind === SyntaxKind.TypeOfKeyword && isTypeOfExpression(parent) ||
1067                node.kind === SyntaxKind.AwaitKeyword && isAwaitExpression(parent) ||
1068                node.kind === SyntaxKind.YieldKeyword && isYieldExpression(parent) ||
1069                node.kind === SyntaxKind.DeleteKeyword && isDeleteExpression(parent)) {
1070                if (parent.expression) {
1071                    return skipOuterExpressions(parent.expression);
1072                }
1073            }
1074            // left /**/in [|name|]
1075            // left /**/instanceof [|name|]
1076            if ((node.kind === SyntaxKind.InKeyword || node.kind === SyntaxKind.InstanceOfKeyword) && isBinaryExpression(parent) && parent.operatorToken === node) {
1077                return skipOuterExpressions(parent.right);
1078            }
1079            // left /**/as [|name|]
1080            if (node.kind === SyntaxKind.AsKeyword && isAsExpression(parent) && isTypeReferenceNode(parent.type)) {
1081                return parent.type.typeName;
1082            }
1083            // for (... /**/in [|name|])
1084            // for (... /**/of [|name|])
1085            if (node.kind === SyntaxKind.InKeyword && isForInStatement(parent) ||
1086                node.kind === SyntaxKind.OfKeyword && isForOfStatement(parent)) {
1087                return skipOuterExpressions(parent.expression);
1088            }
1089        }
1090        return node;
1091    }
1092
1093    /**
1094     * Adjusts the location used for "find references" and "go to definition" when the cursor was not
1095     * on a property name.
1096     */
1097    export function getAdjustedReferenceLocation(node: Node): Node {
1098        return getAdjustedLocation(node, /*forRename*/ false);
1099    }
1100
1101    /**
1102     * Adjusts the location used for "rename" when the cursor was not on a property name.
1103     */
1104    export function getAdjustedRenameLocation(node: Node): Node {
1105        return getAdjustedLocation(node, /*forRename*/ true);
1106    }
1107
1108    /**
1109     * Gets the token whose text has range [start, end) and
1110     * position >= start and (position < end or (position === end && token is literal or keyword or identifier))
1111     */
1112    export function getTouchingPropertyName(sourceFile: SourceFile, position: number): Node {
1113        return getTouchingToken(sourceFile, position, n => isPropertyNameLiteral(n) || isKeyword(n.kind) || isPrivateIdentifier(n));
1114    }
1115
1116    /**
1117     * Returns the token if position is in [start, end).
1118     * If position === end, returns the preceding token if includeItemAtEndPosition(previousToken) === true
1119     */
1120    export function getTouchingToken(sourceFile: SourceFile, position: number, includePrecedingTokenAtEndPosition?: (n: Node) => boolean): Node {
1121        return getTokenAtPositionWorker(sourceFile, position, /*allowPositionInLeadingTrivia*/ false, includePrecedingTokenAtEndPosition, /*includeEndPosition*/ false);
1122    }
1123
1124    /** Returns a token if position is in [start-of-leading-trivia, end) */
1125    export function getTokenAtPosition(sourceFile: SourceFile, position: number): Node {
1126        return getTokenAtPositionWorker(sourceFile, position, /*allowPositionInLeadingTrivia*/ true, /*includePrecedingTokenAtEndPosition*/ undefined, /*includeEndPosition*/ false);
1127    }
1128
1129    /** Get the token whose text contains the position */
1130    function getTokenAtPositionWorker(sourceFile: SourceFile, position: number, allowPositionInLeadingTrivia: boolean, includePrecedingTokenAtEndPosition: ((n: Node) => boolean) | undefined, includeEndPosition: boolean): Node {
1131        let current: Node = sourceFile;
1132        let foundToken: Node | undefined;
1133        outer: while (true) {
1134            // find the child that contains 'position'
1135
1136            const children = current.getChildren(sourceFile);
1137            const i = binarySearchKey(children, position, (_, i) => i, (middle, _) => {
1138                // This last callback is more of a selector than a comparator -
1139                // `EqualTo` causes the `middle` result to be returned
1140                // `GreaterThan` causes recursion on the left of the middle
1141                // `LessThan` causes recursion on the right of the middle
1142
1143                // Let's say you have 3 nodes, spanning positons
1144                // pos: 1, end: 3
1145                // pos: 3, end: 3
1146                // pos: 3, end: 5
1147                // and you're looking for the token at positon 3 - all 3 of these nodes are overlapping with position 3.
1148                // In fact, there's a _good argument_ that node 2 shouldn't even be allowed to exist - depending on if
1149                // the start or end of the ranges are considered inclusive, it's either wholly subsumed by the first or the last node.
1150                // Unfortunately, such nodes do exist. :( - See fourslash/completionsImport_tsx.tsx - empty jsx attributes create
1151                // a zero-length node.
1152                // What also you may not expect is that which node we return depends on the includePrecedingTokenAtEndPosition flag.
1153                // Specifically, if includePrecedingTokenAtEndPosition is set, we return the 1-3 node, while if it's unset, we
1154                // return the 3-5 node. (The zero length node is never correct.) This is because the includePrecedingTokenAtEndPosition
1155                // flag causes us to return the first node whose end position matches the position and which produces and acceptable token
1156                // kind. Meanwhile, if includePrecedingTokenAtEndPosition is unset, we look for the first node whose start is <= the
1157                // position and whose end is greater than the position.
1158
1159
1160                // There are more sophisticated end tests later, but this one is very fast
1161                // and allows us to skip a bunch of work
1162                const end = children[middle].getEnd();
1163                if (end < position) {
1164                    return Comparison.LessThan;
1165                }
1166
1167                const start = allowPositionInLeadingTrivia ? children[middle].getFullStart() : children[middle].getStart(sourceFile, /*includeJsDoc*/ true);
1168                if (start > position) {
1169                    return Comparison.GreaterThan;
1170                }
1171
1172                // first element whose start position is before the input and whose end position is after or equal to the input
1173                if (nodeContainsPosition(children[middle], start, end)) {
1174                    if (children[middle - 1]) {
1175                        // we want the _first_ element that contains the position, so left-recur if the prior node also contains the position
1176                        if (nodeContainsPosition(children[middle - 1])) {
1177                            return Comparison.GreaterThan;
1178                        }
1179                    }
1180                    return Comparison.EqualTo;
1181                }
1182
1183                // this complex condition makes us left-recur around a zero-length node when includePrecedingTokenAtEndPosition is set, rather than right-recur on it
1184                if (includePrecedingTokenAtEndPosition && start === position && children[middle - 1] && children[middle - 1].getEnd() === position && nodeContainsPosition(children[middle - 1])) {
1185                    return Comparison.GreaterThan;
1186                }
1187                return Comparison.LessThan;
1188            });
1189
1190            if (foundToken) {
1191                return foundToken;
1192            }
1193            if (i >= 0 && children[i]) {
1194                current = children[i];
1195                continue outer;
1196            }
1197
1198            return current;
1199        }
1200
1201        function nodeContainsPosition(node: Node, start?: number, end?: number) {
1202            end ??= node.getEnd();
1203            if (end < position) {
1204                return false;
1205            }
1206            start ??= allowPositionInLeadingTrivia ? node.getFullStart() : node.getStart(sourceFile, /*includeJsDoc*/ true);
1207            if (start > position) {
1208                // If this child begins after position, then all subsequent children will as well.
1209                return false;
1210            }
1211            if (position < end || (position === end && (node.kind === SyntaxKind.EndOfFileToken || includeEndPosition))) {
1212                return true;
1213            }
1214            else if (includePrecedingTokenAtEndPosition && end === position) {
1215                const previousToken = findPrecedingToken(position, sourceFile, node);
1216                if (previousToken && includePrecedingTokenAtEndPosition(previousToken)) {
1217                    foundToken = previousToken;
1218                    return true;
1219                }
1220            }
1221            return false;
1222        }
1223    }
1224
1225    /**
1226     * Returns the first token where position is in [start, end),
1227     * excluding `JsxText` tokens containing only whitespace.
1228     */
1229    export function findFirstNonJsxWhitespaceToken(sourceFile: SourceFile, position: number): Node | undefined {
1230        let tokenAtPosition = getTokenAtPosition(sourceFile, position);
1231        while (isWhiteSpaceOnlyJsxText(tokenAtPosition)) {
1232            const nextToken = findNextToken(tokenAtPosition, tokenAtPosition.parent, sourceFile);
1233            if (!nextToken) return;
1234            tokenAtPosition = nextToken;
1235        }
1236        return tokenAtPosition;
1237    }
1238
1239    /**
1240     * The token on the left of the position is the token that strictly includes the position
1241     * or sits to the left of the cursor if it is on a boundary. For example
1242     *
1243     *   fo|o               -> will return foo
1244     *   foo <comment> |bar -> will return foo
1245     *
1246     */
1247    export function findTokenOnLeftOfPosition(file: SourceFile, position: number): Node | undefined {
1248        // Ideally, getTokenAtPosition should return a token. However, it is currently
1249        // broken, so we do a check to make sure the result was indeed a token.
1250        const tokenAtPosition = getTokenAtPosition(file, position);
1251        if (isToken(tokenAtPosition) && position > tokenAtPosition.getStart(file) && position < tokenAtPosition.getEnd()) {
1252            return tokenAtPosition;
1253        }
1254
1255        return findPrecedingToken(position, file);
1256    }
1257
1258    export function findNextToken(previousToken: Node, parent: Node, sourceFile: SourceFileLike): Node | undefined {
1259        return find(parent);
1260
1261        function find(n: Node): Node | undefined {
1262            if (isToken(n) && n.pos === previousToken.end) {
1263                // this is token that starts at the end of previous token - return it
1264                return n;
1265            }
1266            return firstDefined(n.getChildren(sourceFile), child => {
1267                const shouldDiveInChildNode =
1268                    // previous token is enclosed somewhere in the child
1269                    (child.pos <= previousToken.pos && child.end > previousToken.end) ||
1270                    // previous token ends exactly at the beginning of child
1271                    (child.pos === previousToken.end);
1272                return shouldDiveInChildNode && nodeHasTokens(child, sourceFile) ? find(child) : undefined;
1273            });
1274        }
1275    }
1276
1277    /**
1278     * Finds the rightmost token satisfying `token.end <= position`,
1279     * excluding `JsxText` tokens containing only whitespace.
1280     */
1281    export function findPrecedingToken(position: number, sourceFile: SourceFileLike, startNode: Node, excludeJsdoc?: boolean): Node | undefined;
1282    export function findPrecedingToken(position: number, sourceFile: SourceFile, startNode?: Node, excludeJsdoc?: boolean): Node | undefined;
1283    export function findPrecedingToken(position: number, sourceFile: SourceFileLike, startNode?: Node, excludeJsdoc?: boolean): Node | undefined {
1284        const result = find((startNode || sourceFile) as Node);
1285        Debug.assert(!(result && isWhiteSpaceOnlyJsxText(result)));
1286        return result;
1287
1288        function find(n: Node): Node | undefined {
1289            if (isNonWhitespaceToken(n) && n.kind !== SyntaxKind.EndOfFileToken) {
1290                return n;
1291            }
1292
1293            const children = n.getChildren(sourceFile);
1294            const i = binarySearchKey(children, position, (_, i) => i, (middle, _) => {
1295                // This last callback is more of a selector than a comparator -
1296                // `EqualTo` causes the `middle` result to be returned
1297                // `GreaterThan` causes recursion on the left of the middle
1298                // `LessThan` causes recursion on the right of the middle
1299                if (position < children[middle].end) {
1300                    // first element whose end position is greater than the input position
1301                    if (!children[middle - 1] || position >= children[middle - 1].end) {
1302                        return Comparison.EqualTo;
1303                    }
1304                    return Comparison.GreaterThan;
1305                }
1306                return Comparison.LessThan;
1307            });
1308            if (i >= 0 && children[i]) {
1309                const child = children[i];
1310                // Note that the span of a node's tokens is [node.getStart(...), node.end).
1311                // Given that `position < child.end` and child has constituent tokens, we distinguish these cases:
1312                // 1) `position` precedes `child`'s tokens or `child` has no tokens (ie: in a comment or whitespace preceding `child`):
1313                // we need to find the last token in a previous child.
1314                // 2) `position` is within the same span: we recurse on `child`.
1315                if (position < child.end) {
1316                    const start = child.getStart(sourceFile, /*includeJsDoc*/ !excludeJsdoc);
1317                    const lookInPreviousChild =
1318                        (start >= position) || // cursor in the leading trivia
1319                        !nodeHasTokens(child, sourceFile) ||
1320                        isWhiteSpaceOnlyJsxText(child);
1321
1322                    if (lookInPreviousChild) {
1323                        // actual start of the node is past the position - previous token should be at the end of previous child
1324                        const candidate = findRightmostChildNodeWithTokens(children, /*exclusiveStartPosition*/ i, sourceFile, n.kind);
1325                        return candidate && findRightmostToken(candidate, sourceFile);
1326                    }
1327                    else {
1328                        // candidate should be in this node
1329                        return find(child);
1330                    }
1331                }
1332            }
1333
1334            Debug.assert(startNode !== undefined || n.kind === SyntaxKind.SourceFile || n.kind === SyntaxKind.EndOfFileToken || isJSDocCommentContainingNode(n));
1335
1336            // Here we know that none of child token nodes embrace the position,
1337            // the only known case is when position is at the end of the file.
1338            // Try to find the rightmost token in the file without filtering.
1339            // Namely we are skipping the check: 'position < node.end'
1340            const candidate = findRightmostChildNodeWithTokens(children, /*exclusiveStartPosition*/ children.length, sourceFile, n.kind);
1341            return candidate && findRightmostToken(candidate, sourceFile);
1342        }
1343    }
1344
1345    function isNonWhitespaceToken(n: Node): boolean {
1346        return isToken(n) && !isWhiteSpaceOnlyJsxText(n);
1347    }
1348
1349    function findRightmostToken(n: Node, sourceFile: SourceFileLike): Node | undefined {
1350        if (isNonWhitespaceToken(n)) {
1351            return n;
1352        }
1353
1354        const children = n.getChildren(sourceFile);
1355        if (children.length === 0) {
1356            return n;
1357        }
1358
1359        const candidate = findRightmostChildNodeWithTokens(children, /*exclusiveStartPosition*/ children.length, sourceFile, n.kind);
1360        return candidate && findRightmostToken(candidate, sourceFile);
1361    }
1362
1363    /**
1364     * Finds the rightmost child to the left of `children[exclusiveStartPosition]` which is a non-all-whitespace token or has constituent tokens.
1365     */
1366    function findRightmostChildNodeWithTokens(children: Node[], exclusiveStartPosition: number, sourceFile: SourceFileLike, parentKind: SyntaxKind): Node | undefined {
1367        for (let i = exclusiveStartPosition - 1; i >= 0; i--) {
1368            const child = children[i];
1369
1370            if (isWhiteSpaceOnlyJsxText(child)) {
1371                if (i === 0 && (parentKind === SyntaxKind.JsxText || parentKind === SyntaxKind.JsxSelfClosingElement)) {
1372                    Debug.fail("`JsxText` tokens should not be the first child of `JsxElement | JsxSelfClosingElement`");
1373                }
1374            }
1375            else if (nodeHasTokens(children[i], sourceFile)) {
1376                return children[i];
1377            }
1378        }
1379    }
1380
1381    export function isInString(sourceFile: SourceFile, position: number, previousToken = findPrecedingToken(position, sourceFile)): boolean {
1382        if (previousToken && isStringTextContainingNode(previousToken)) {
1383            const start = previousToken.getStart(sourceFile);
1384            const end = previousToken.getEnd();
1385
1386            // To be "in" one of these literals, the position has to be:
1387            //   1. entirely within the token text.
1388            //   2. at the end position of an unterminated token.
1389            //   3. at the end of a regular expression (due to trailing flags like '/foo/g').
1390            if (start < position && position < end) {
1391                return true;
1392            }
1393
1394            if (position === end) {
1395                return !!(previousToken as LiteralExpression).isUnterminated;
1396            }
1397        }
1398
1399        return false;
1400    }
1401
1402    /**
1403     * returns true if the position is in between the open and close elements of an JSX expression.
1404     */
1405    export function isInsideJsxElementOrAttribute(sourceFile: SourceFile, position: number) {
1406        const token = getTokenAtPosition(sourceFile, position);
1407
1408        if (!token) {
1409            return false;
1410        }
1411
1412        if (token.kind === SyntaxKind.JsxText) {
1413            return true;
1414        }
1415
1416        // <div>Hello |</div>
1417        if (token.kind === SyntaxKind.LessThanToken && token.parent.kind === SyntaxKind.JsxText) {
1418            return true;
1419        }
1420
1421        // <div> { | </div> or <div a={| </div>
1422        if (token.kind === SyntaxKind.LessThanToken && token.parent.kind === SyntaxKind.JsxExpression) {
1423            return true;
1424        }
1425
1426        // <div> {
1427        // |
1428        // } < /div>
1429        if (token && token.kind === SyntaxKind.CloseBraceToken && token.parent.kind === SyntaxKind.JsxExpression) {
1430            return true;
1431        }
1432
1433        // <div>|</div>
1434        if (token.kind === SyntaxKind.LessThanToken && token.parent.kind === SyntaxKind.JsxClosingElement) {
1435            return true;
1436        }
1437
1438        return false;
1439    }
1440
1441    function isWhiteSpaceOnlyJsxText(node: Node): boolean {
1442        return isJsxText(node) && node.containsOnlyTriviaWhiteSpaces;
1443    }
1444
1445    export function isInTemplateString(sourceFile: SourceFile, position: number) {
1446        const token = getTokenAtPosition(sourceFile, position);
1447        return isTemplateLiteralKind(token.kind) && position > token.getStart(sourceFile);
1448    }
1449
1450    export function isInJSXText(sourceFile: SourceFile, position: number) {
1451        const token = getTokenAtPosition(sourceFile, position);
1452        if (isJsxText(token)) {
1453            return true;
1454        }
1455        if (token.kind === SyntaxKind.OpenBraceToken && isJsxExpression(token.parent) && isJsxElement(token.parent.parent)) {
1456            return true;
1457        }
1458        if (token.kind === SyntaxKind.LessThanToken && isJsxOpeningLikeElement(token.parent) && isJsxElement(token.parent.parent)) {
1459            return true;
1460        }
1461        return false;
1462    }
1463
1464    export function isInsideJsxElement(sourceFile: SourceFile, position: number): boolean {
1465        function isInsideJsxElementTraversal(node: Node): boolean {
1466            while (node) {
1467                if (node.kind >= SyntaxKind.JsxSelfClosingElement && node.kind <= SyntaxKind.JsxExpression
1468                    || node.kind === SyntaxKind.JsxText
1469                    || node.kind === SyntaxKind.LessThanToken
1470                    || node.kind === SyntaxKind.GreaterThanToken
1471                    || node.kind === SyntaxKind.Identifier
1472                    || node.kind === SyntaxKind.CloseBraceToken
1473                    || node.kind === SyntaxKind.OpenBraceToken
1474                    || node.kind === SyntaxKind.SlashToken) {
1475                    node = node.parent;
1476                }
1477                else if (node.kind === SyntaxKind.JsxElement) {
1478                    if (position > node.getStart(sourceFile)) return true;
1479
1480                    node = node.parent;
1481                }
1482                else {
1483                    return false;
1484                }
1485            }
1486
1487            return false;
1488        }
1489
1490        return isInsideJsxElementTraversal(getTokenAtPosition(sourceFile, position));
1491    }
1492
1493    export function findPrecedingMatchingToken(token: Node, matchingTokenKind: SyntaxKind.OpenBraceToken | SyntaxKind.OpenParenToken | SyntaxKind.OpenBracketToken, sourceFile: SourceFile) {
1494        const closeTokenText = tokenToString(token.kind)!;
1495        const matchingTokenText = tokenToString(matchingTokenKind)!;
1496        const tokenFullStart = token.getFullStart();
1497        // Text-scan based fast path - can be bamboozled by comments and other trivia, but often provides
1498        // a good, fast approximation without too much extra work in the cases where it fails.
1499        const bestGuessIndex = sourceFile.text.lastIndexOf(matchingTokenText, tokenFullStart);
1500        if (bestGuessIndex === -1) {
1501            return undefined; // if the token text doesn't appear in the file, there can't be a match - super fast bail
1502        }
1503        // we can only use the textual result directly if we didn't have to count any close tokens within the range
1504        if (sourceFile.text.lastIndexOf(closeTokenText, tokenFullStart - 1) < bestGuessIndex) {
1505            const nodeAtGuess = findPrecedingToken(bestGuessIndex + 1, sourceFile);
1506            if (nodeAtGuess && nodeAtGuess.kind === matchingTokenKind) {
1507                return nodeAtGuess;
1508            }
1509        }
1510        const tokenKind = token.kind;
1511        let remainingMatchingTokens = 0;
1512        while (true) {
1513            const preceding = findPrecedingToken(token.getFullStart(), sourceFile);
1514            if (!preceding) {
1515                return undefined;
1516            }
1517            token = preceding;
1518
1519            if (token.kind === matchingTokenKind) {
1520                if (remainingMatchingTokens === 0) {
1521                    return token;
1522                }
1523
1524                remainingMatchingTokens--;
1525            }
1526            else if (token.kind === tokenKind) {
1527                remainingMatchingTokens++;
1528            }
1529        }
1530    }
1531
1532    export function removeOptionality(type: Type, isOptionalExpression: boolean, isOptionalChain: boolean) {
1533        return isOptionalExpression ? type.getNonNullableType() :
1534            isOptionalChain ? type.getNonOptionalType() :
1535                type;
1536    }
1537
1538    export function isPossiblyTypeArgumentPosition(token: Node, sourceFile: SourceFile, checker: TypeChecker): boolean {
1539        const info = getPossibleTypeArgumentsInfo(token, sourceFile);
1540        return info !== undefined && (isPartOfTypeNode(info.called) ||
1541            getPossibleGenericSignatures(info.called, info.nTypeArguments, checker).length !== 0 ||
1542            isPossiblyTypeArgumentPosition(info.called, sourceFile, checker));
1543    }
1544
1545    export function getPossibleGenericSignatures(called: Expression, typeArgumentCount: number, checker: TypeChecker): readonly Signature[] {
1546        let type = checker.getTypeAtLocation(called);
1547        if (isOptionalChain(called.parent)) {
1548            type = removeOptionality(type, isOptionalChainRoot(called.parent), /*isOptionalChain*/ true);
1549        }
1550
1551        const signatures = isNewExpression(called.parent) ? type.getConstructSignatures() : type.getCallSignatures();
1552        return signatures.filter(candidate => !!candidate.typeParameters && candidate.typeParameters.length >= typeArgumentCount);
1553    }
1554
1555    export interface PossibleTypeArgumentInfo {
1556        readonly called: Identifier;
1557        readonly nTypeArguments: number;
1558    }
1559
1560    export interface PossibleProgramFileInfo {
1561        ProgramFiles?: string[];
1562    }
1563
1564    // Get info for an expression like `f <` that may be the start of type arguments.
1565    export function getPossibleTypeArgumentsInfo(tokenIn: Node | undefined, sourceFile: SourceFile): PossibleTypeArgumentInfo | undefined {
1566        // This is a rare case, but one that saves on a _lot_ of work if true - if the source file has _no_ `<` character,
1567        // then there obviously can't be any type arguments - no expensive brace-matching backwards scanning required
1568
1569        if (sourceFile.text.lastIndexOf("<", tokenIn ? tokenIn.pos : sourceFile.text.length) === -1) {
1570            return undefined;
1571        }
1572
1573        let token: Node | undefined = tokenIn;
1574        // This function determines if the node could be type argument position
1575        // Since during editing, when type argument list is not complete,
1576        // the tree could be of any shape depending on the tokens parsed before current node,
1577        // scanning of the previous identifier followed by "<" before current node would give us better result
1578        // Note that we also balance out the already provided type arguments, arrays, object literals while doing so
1579        let remainingLessThanTokens = 0;
1580        let nTypeArguments = 0;
1581        while (token) {
1582            switch (token.kind) {
1583                case SyntaxKind.LessThanToken:
1584                    // Found the beginning of the generic argument expression
1585                    token = findPrecedingToken(token.getFullStart(), sourceFile);
1586                    if (token && token.kind === SyntaxKind.QuestionDotToken) {
1587                        token = findPrecedingToken(token.getFullStart(), sourceFile);
1588                    }
1589                    if (!token || !isIdentifier(token)) return undefined;
1590                    if (!remainingLessThanTokens) {
1591                        return isDeclarationName(token) ? undefined : { called: token, nTypeArguments };
1592                    }
1593                    remainingLessThanTokens--;
1594                    break;
1595
1596                case SyntaxKind.GreaterThanGreaterThanGreaterThanToken:
1597                    remainingLessThanTokens = + 3;
1598                    break;
1599
1600                case SyntaxKind.GreaterThanGreaterThanToken:
1601                    remainingLessThanTokens = + 2;
1602                    break;
1603
1604                case SyntaxKind.GreaterThanToken:
1605                    remainingLessThanTokens++;
1606                    break;
1607
1608                case SyntaxKind.CloseBraceToken:
1609                    // This can be object type, skip until we find the matching open brace token
1610                    // Skip until the matching open brace token
1611                    token = findPrecedingMatchingToken(token, SyntaxKind.OpenBraceToken, sourceFile);
1612                    if (!token) return undefined;
1613                    break;
1614
1615                case SyntaxKind.CloseParenToken:
1616                    // This can be object type, skip until we find the matching open brace token
1617                    // Skip until the matching open brace token
1618                    token = findPrecedingMatchingToken(token, SyntaxKind.OpenParenToken, sourceFile);
1619                    if (!token) return undefined;
1620                    break;
1621
1622                case SyntaxKind.CloseBracketToken:
1623                    // This can be object type, skip until we find the matching open brace token
1624                    // Skip until the matching open brace token
1625                    token = findPrecedingMatchingToken(token, SyntaxKind.OpenBracketToken, sourceFile);
1626                    if (!token) return undefined;
1627                    break;
1628
1629                // Valid tokens in a type name. Skip.
1630                case SyntaxKind.CommaToken:
1631                    nTypeArguments++;
1632                    break;
1633
1634                case SyntaxKind.EqualsGreaterThanToken:
1635                // falls through
1636
1637                case SyntaxKind.Identifier:
1638                case SyntaxKind.StringLiteral:
1639                case SyntaxKind.NumericLiteral:
1640                case SyntaxKind.BigIntLiteral:
1641                case SyntaxKind.TrueKeyword:
1642                case SyntaxKind.FalseKeyword:
1643                // falls through
1644
1645                case SyntaxKind.TypeOfKeyword:
1646                case SyntaxKind.ExtendsKeyword:
1647                case SyntaxKind.KeyOfKeyword:
1648                case SyntaxKind.DotToken:
1649                case SyntaxKind.BarToken:
1650                case SyntaxKind.QuestionToken:
1651                case SyntaxKind.ColonToken:
1652                    break;
1653
1654                default:
1655                    if (isTypeNode(token)) {
1656                        break;
1657                    }
1658
1659                    // Invalid token in type
1660                    return undefined;
1661            }
1662
1663            token = findPrecedingToken(token.getFullStart(), sourceFile);
1664        }
1665
1666        return undefined;
1667    }
1668
1669    /**
1670     * Returns true if the cursor at position in sourceFile is within a comment.
1671     *
1672     * @param tokenAtPosition Must equal `getTokenAtPosition(sourceFile, position)`
1673     * @param predicate Additional predicate to test on the comment range.
1674     */
1675    export function isInComment(sourceFile: SourceFile, position: number, tokenAtPosition?: Node): CommentRange | undefined {
1676        return formatting.getRangeOfEnclosingComment(sourceFile, position, /*precedingToken*/ undefined, tokenAtPosition);
1677    }
1678
1679    export function hasDocComment(sourceFile: SourceFile, position: number): boolean {
1680        const token = getTokenAtPosition(sourceFile, position);
1681        return !!findAncestor(token, isJSDoc);
1682    }
1683
1684    function nodeHasTokens(n: Node, sourceFile: SourceFileLike): boolean {
1685        // If we have a token or node that has a non-zero width, it must have tokens.
1686        // Note: getWidth() does not take trivia into account.
1687        return n.kind === SyntaxKind.EndOfFileToken ? !!(n as EndOfFileToken).jsDoc : n.getWidth(sourceFile) !== 0;
1688    }
1689
1690    export function getNodeModifiers(node: Node, excludeFlags = ModifierFlags.None): string {
1691        const result: string[] = [];
1692        const flags = isDeclaration(node)
1693            ? getCombinedNodeFlagsAlwaysIncludeJSDoc(node) & ~excludeFlags
1694            : ModifierFlags.None;
1695
1696        if (flags & ModifierFlags.Private) result.push(ScriptElementKindModifier.privateMemberModifier);
1697        if (flags & ModifierFlags.Protected) result.push(ScriptElementKindModifier.protectedMemberModifier);
1698        if (flags & ModifierFlags.Public) result.push(ScriptElementKindModifier.publicMemberModifier);
1699        if (flags & ModifierFlags.Static || isClassStaticBlockDeclaration(node)) result.push(ScriptElementKindModifier.staticModifier);
1700        if (flags & ModifierFlags.Abstract) result.push(ScriptElementKindModifier.abstractModifier);
1701        if (flags & ModifierFlags.Export) result.push(ScriptElementKindModifier.exportedModifier);
1702        if (flags & ModifierFlags.Deprecated) result.push(ScriptElementKindModifier.deprecatedModifier);
1703        if (node.flags & NodeFlags.Ambient) result.push(ScriptElementKindModifier.ambientModifier);
1704        if (node.kind === SyntaxKind.ExportAssignment) result.push(ScriptElementKindModifier.exportedModifier);
1705
1706        return result.length > 0 ? result.join(",") : ScriptElementKindModifier.none;
1707    }
1708
1709    export function getTypeArgumentOrTypeParameterList(node: Node): NodeArray<Node> | undefined {
1710        if (node.kind === SyntaxKind.TypeReference || node.kind === SyntaxKind.CallExpression) {
1711            return (node as CallExpression).typeArguments;
1712        }
1713
1714        if (isFunctionLike(node) || node.kind === SyntaxKind.ClassDeclaration || node.kind === SyntaxKind.InterfaceDeclaration) {
1715            return (node as FunctionLikeDeclaration).typeParameters;
1716        }
1717
1718        return undefined;
1719    }
1720
1721    export function isComment(kind: SyntaxKind): boolean {
1722        return kind === SyntaxKind.SingleLineCommentTrivia || kind === SyntaxKind.MultiLineCommentTrivia;
1723    }
1724
1725    export function isStringOrRegularExpressionOrTemplateLiteral(kind: SyntaxKind): boolean {
1726        if (kind === SyntaxKind.StringLiteral
1727            || kind === SyntaxKind.RegularExpressionLiteral
1728            || isTemplateLiteralKind(kind)) {
1729            return true;
1730        }
1731        return false;
1732    }
1733
1734    export function isPunctuation(kind: SyntaxKind): boolean {
1735        return SyntaxKind.FirstPunctuation <= kind && kind <= SyntaxKind.LastPunctuation;
1736    }
1737
1738    export function isInsideTemplateLiteral(node: TemplateLiteralToken, position: number, sourceFile: SourceFile): boolean {
1739        return isTemplateLiteralKind(node.kind)
1740            && (node.getStart(sourceFile) < position && position < node.end) || (!!node.isUnterminated && position === node.end);
1741    }
1742
1743    export function isAccessibilityModifier(kind: SyntaxKind) {
1744        switch (kind) {
1745            case SyntaxKind.PublicKeyword:
1746            case SyntaxKind.PrivateKeyword:
1747            case SyntaxKind.ProtectedKeyword:
1748                return true;
1749        }
1750
1751        return false;
1752    }
1753
1754    export function cloneCompilerOptions(options: CompilerOptions): CompilerOptions {
1755        const result = clone(options);
1756        setConfigFileInOptions(result, options && options.configFile);
1757        return result;
1758    }
1759
1760    export function isArrayLiteralOrObjectLiteralDestructuringPattern(node: Node) {
1761        if (node.kind === SyntaxKind.ArrayLiteralExpression ||
1762            node.kind === SyntaxKind.ObjectLiteralExpression) {
1763            // [a,b,c] from:
1764            // [a, b, c] = someExpression;
1765            if (node.parent.kind === SyntaxKind.BinaryExpression &&
1766                (node.parent as BinaryExpression).left === node &&
1767                (node.parent as BinaryExpression).operatorToken.kind === SyntaxKind.EqualsToken) {
1768                return true;
1769            }
1770
1771            // [a, b, c] from:
1772            // for([a, b, c] of expression)
1773            if (node.parent.kind === SyntaxKind.ForOfStatement &&
1774                (node.parent as ForOfStatement).initializer === node) {
1775                return true;
1776            }
1777
1778            // [a, b, c] of
1779            // [x, [a, b, c] ] = someExpression
1780            // or
1781            // {x, a: {a, b, c} } = someExpression
1782            if (isArrayLiteralOrObjectLiteralDestructuringPattern(node.parent.kind === SyntaxKind.PropertyAssignment ? node.parent.parent : node.parent)) {
1783                return true;
1784            }
1785        }
1786
1787        return false;
1788    }
1789
1790    export function isInReferenceComment(sourceFile: SourceFile, position: number): boolean {
1791        return isInReferenceCommentWorker(sourceFile, position, /*shouldBeReference*/ true);
1792    }
1793
1794    export function isInNonReferenceComment(sourceFile: SourceFile, position: number): boolean {
1795        return isInReferenceCommentWorker(sourceFile, position, /*shouldBeReference*/ false);
1796    }
1797
1798    function isInReferenceCommentWorker(sourceFile: SourceFile, position: number, shouldBeReference: boolean): boolean {
1799        const range = isInComment(sourceFile, position, /*tokenAtPosition*/ undefined);
1800        return !!range && shouldBeReference === tripleSlashDirectivePrefixRegex.test(sourceFile.text.substring(range.pos, range.end));
1801    }
1802
1803    export function getReplacementSpanForContextToken(contextToken: Node | undefined) {
1804        if (!contextToken) return undefined;
1805
1806        switch (contextToken.kind) {
1807            case SyntaxKind.StringLiteral:
1808            case SyntaxKind.NoSubstitutionTemplateLiteral:
1809                return createTextSpanFromStringLiteralLikeContent(contextToken as StringLiteralLike);
1810            default:
1811                return createTextSpanFromNode(contextToken);
1812        }
1813    }
1814
1815    export function createTextSpanFromNode(node: Node, sourceFile?: SourceFile, endNode?: Node): TextSpan {
1816        return createTextSpanFromBounds(node.getStart(sourceFile), (endNode || node).getEnd());
1817    }
1818
1819    export function createTextSpanFromStringLiteralLikeContent(node: StringLiteralLike) {
1820        if (node.isUnterminated) return undefined;
1821        return createTextSpanFromBounds(node.getStart() + 1, node.getEnd() - 1);
1822    }
1823
1824    export function createTextRangeFromNode(node: Node, sourceFile: SourceFile): TextRange {
1825        return createRange(node.getStart(sourceFile), node.end);
1826    }
1827
1828    export function createTextSpanFromRange(range: TextRange): TextSpan {
1829        return createTextSpanFromBounds(range.pos, range.end);
1830    }
1831
1832    export function createTextRangeFromSpan(span: TextSpan): TextRange {
1833        return createRange(span.start, span.start + span.length);
1834    }
1835
1836    export function createTextChangeFromStartLength(start: number, length: number, newText: string): TextChange {
1837        return createTextChange(createTextSpan(start, length), newText);
1838    }
1839
1840    export function createTextChange(span: TextSpan, newText: string): TextChange {
1841        return { span, newText };
1842    }
1843
1844    export const typeKeywords: readonly SyntaxKind[] = [
1845        SyntaxKind.AnyKeyword,
1846        SyntaxKind.AssertsKeyword,
1847        SyntaxKind.BigIntKeyword,
1848        SyntaxKind.BooleanKeyword,
1849        SyntaxKind.FalseKeyword,
1850        SyntaxKind.InferKeyword,
1851        SyntaxKind.KeyOfKeyword,
1852        SyntaxKind.NeverKeyword,
1853        SyntaxKind.NullKeyword,
1854        SyntaxKind.NumberKeyword,
1855        SyntaxKind.ObjectKeyword,
1856        SyntaxKind.ReadonlyKeyword,
1857        SyntaxKind.StringKeyword,
1858        SyntaxKind.SymbolKeyword,
1859        SyntaxKind.TrueKeyword,
1860        SyntaxKind.VoidKeyword,
1861        SyntaxKind.UndefinedKeyword,
1862        SyntaxKind.UniqueKeyword,
1863        SyntaxKind.UnknownKeyword,
1864    ];
1865
1866    export function isTypeKeyword(kind: SyntaxKind): boolean {
1867        return contains(typeKeywords, kind);
1868    }
1869
1870    export function isTypeKeywordToken(node: Node): node is Token<SyntaxKind.TypeKeyword> {
1871        return node.kind === SyntaxKind.TypeKeyword;
1872    }
1873
1874    export function isTypeKeywordTokenOrIdentifier(node: Node) {
1875        return isTypeKeywordToken(node) || isIdentifier(node) && node.text === "type";
1876    }
1877
1878    /** True if the symbol is for an external module, as opposed to a namespace. */
1879    export function isExternalModuleSymbol(moduleSymbol: Symbol): boolean {
1880        return !!(moduleSymbol.flags & SymbolFlags.Module) && moduleSymbol.name.charCodeAt(0) === CharacterCodes.doubleQuote;
1881    }
1882
1883    /** Returns `true` the first time it encounters a node and `false` afterwards. */
1884    export type NodeSeenTracker<T = Node> = (node: T) => boolean;
1885    export function nodeSeenTracker<T extends Node>(): NodeSeenTracker<T> {
1886        const seen: true[] = [];
1887        return node => {
1888            const id = getNodeId(node);
1889            return !seen[id] && (seen[id] = true);
1890        };
1891    }
1892
1893    export function getSnapshotText(snap: IScriptSnapshot): string {
1894        return snap.getText(0, snap.getLength());
1895    }
1896
1897    export function repeatString(str: string, count: number): string {
1898        let result = "";
1899        for (let i = 0; i < count; i++) {
1900            result += str;
1901        }
1902        return result;
1903    }
1904
1905    export function skipConstraint(type: Type): Type {
1906        return type.isTypeParameter() ? type.getConstraint() || type : type;
1907    }
1908
1909    export function getNameFromPropertyName(name: PropertyName): string | undefined {
1910        return name.kind === SyntaxKind.ComputedPropertyName
1911            // treat computed property names where expression is string/numeric literal as just string/numeric literal
1912            ? isStringOrNumericLiteralLike(name.expression) ? name.expression.text : undefined
1913            : isPrivateIdentifier(name) ? idText(name) : getTextOfIdentifierOrLiteral(name);
1914    }
1915
1916    export function programContainsModules(program: Program): boolean {
1917        return program.getSourceFiles().some(s => !s.isDeclarationFile && !program.isSourceFileFromExternalLibrary(s) && !!(s.externalModuleIndicator || s.commonJsModuleIndicator));
1918    }
1919    export function programContainsEsModules(program: Program): boolean {
1920        return program.getSourceFiles().some(s => !s.isDeclarationFile && !program.isSourceFileFromExternalLibrary(s) && !!s.externalModuleIndicator);
1921    }
1922    export function compilerOptionsIndicateEsModules(compilerOptions: CompilerOptions): boolean {
1923        return !!compilerOptions.module || getEmitScriptTarget(compilerOptions) >= ScriptTarget.ES2015 || !!compilerOptions.noEmit;
1924    }
1925
1926    export function createModuleSpecifierResolutionHost(program: Program, host: LanguageServiceHost): ModuleSpecifierResolutionHost {
1927        // Mix in `getSymlinkCache` from Program when host doesn't have it
1928        // in order for non-Project hosts to have a symlinks cache.
1929        return {
1930            fileExists: fileName => program.fileExists(fileName),
1931            getCurrentDirectory: () => host.getCurrentDirectory(),
1932            readFile: maybeBind(host, host.readFile),
1933            useCaseSensitiveFileNames: maybeBind(host, host.useCaseSensitiveFileNames),
1934            getSymlinkCache: maybeBind(host, host.getSymlinkCache) || program.getSymlinkCache,
1935            getModuleSpecifierCache: maybeBind(host, host.getModuleSpecifierCache),
1936            getPackageJsonInfoCache: () => program.getModuleResolutionCache()?.getPackageJsonInfoCache(),
1937            getGlobalTypingsCacheLocation: maybeBind(host, host.getGlobalTypingsCacheLocation),
1938            redirectTargetsMap: program.redirectTargetsMap,
1939            getProjectReferenceRedirect: fileName => program.getProjectReferenceRedirect(fileName),
1940            isSourceOfProjectReferenceRedirect: fileName => program.isSourceOfProjectReferenceRedirect(fileName),
1941            getNearestAncestorDirectoryWithPackageJson: maybeBind(host, host.getNearestAncestorDirectoryWithPackageJson),
1942            getFileIncludeReasons: () => program.getFileIncludeReasons(),
1943        };
1944    }
1945
1946    export function getModuleSpecifierResolverHost(program: Program, host: LanguageServiceHost): SymbolTracker["moduleResolverHost"] {
1947        return {
1948            ...createModuleSpecifierResolutionHost(program, host),
1949            getCommonSourceDirectory: () => program.getCommonSourceDirectory(),
1950        };
1951    }
1952
1953    export function moduleResolutionRespectsExports(moduleResolution: ModuleResolutionKind): boolean {
1954        return moduleResolution >= ModuleResolutionKind.Node16 && moduleResolution <= ModuleResolutionKind.NodeNext;
1955    }
1956
1957    export function moduleResolutionUsesNodeModules(moduleResolution: ModuleResolutionKind): boolean {
1958        return moduleResolution === ModuleResolutionKind.NodeJs || moduleResolution >= ModuleResolutionKind.Node16 && moduleResolution <= ModuleResolutionKind.NodeNext;
1959    }
1960
1961    export function makeImportIfNecessary(defaultImport: Identifier | undefined, namedImports: readonly ImportSpecifier[] | undefined, moduleSpecifier: string, quotePreference: QuotePreference): ImportDeclaration | undefined {
1962        return defaultImport || namedImports && namedImports.length ? makeImport(defaultImport, namedImports, moduleSpecifier, quotePreference) : undefined;
1963    }
1964
1965    export function makeImport(defaultImport: Identifier | undefined, namedImports: readonly ImportSpecifier[] | undefined, moduleSpecifier: string | Expression, quotePreference: QuotePreference, isTypeOnly?: boolean): ImportDeclaration {
1966        return factory.createImportDeclaration(
1967            /*modifiers*/ undefined,
1968            defaultImport || namedImports
1969                ? factory.createImportClause(!!isTypeOnly, defaultImport, namedImports && namedImports.length ? factory.createNamedImports(namedImports) : undefined)
1970                : undefined,
1971            typeof moduleSpecifier === "string" ? makeStringLiteral(moduleSpecifier, quotePreference) : moduleSpecifier,
1972            /*assertClause*/ undefined);
1973    }
1974
1975    export function makeStringLiteral(text: string, quotePreference: QuotePreference): StringLiteral {
1976        return factory.createStringLiteral(text, quotePreference === QuotePreference.Single);
1977    }
1978
1979    export const enum QuotePreference { Single, Double }
1980
1981    export function quotePreferenceFromString(str: StringLiteral, sourceFile: SourceFile): QuotePreference {
1982        return isStringDoubleQuoted(str, sourceFile) ? QuotePreference.Double : QuotePreference.Single;
1983    }
1984
1985    export function getQuotePreference(sourceFile: SourceFile, preferences: UserPreferences): QuotePreference {
1986        if (preferences.quotePreference && preferences.quotePreference !== "auto") {
1987            return preferences.quotePreference === "single" ? QuotePreference.Single : QuotePreference.Double;
1988        }
1989        else {
1990            // ignore synthetic import added when importHelpers: true
1991            const firstModuleSpecifier = sourceFile.imports &&
1992                find(sourceFile.imports, n => isStringLiteral(n) && !nodeIsSynthesized(n.parent)) as StringLiteral;
1993            return firstModuleSpecifier ? quotePreferenceFromString(firstModuleSpecifier, sourceFile) : QuotePreference.Double;
1994        }
1995    }
1996
1997    export function getQuoteFromPreference(qp: QuotePreference): string {
1998        switch (qp) {
1999            case QuotePreference.Single: return "'";
2000            case QuotePreference.Double: return '"';
2001            default: return Debug.assertNever(qp);
2002        }
2003    }
2004
2005    export function symbolNameNoDefault(symbol: Symbol): string | undefined {
2006        const escaped = symbolEscapedNameNoDefault(symbol);
2007        return escaped === undefined ? undefined : unescapeLeadingUnderscores(escaped);
2008    }
2009
2010    export function symbolEscapedNameNoDefault(symbol: Symbol): __String | undefined {
2011        if (symbol.escapedName !== InternalSymbolName.Default) {
2012            return symbol.escapedName;
2013        }
2014
2015        return firstDefined(symbol.declarations, decl => {
2016            const name = getNameOfDeclaration(decl);
2017            return name && name.kind === SyntaxKind.Identifier ? name.escapedText : undefined;
2018        });
2019    }
2020
2021    export function isModuleSpecifierLike(node: Node): node is StringLiteralLike {
2022        return isStringLiteralLike(node) && (
2023            isExternalModuleReference(node.parent) ||
2024            isImportDeclaration(node.parent) ||
2025            isRequireCall(node.parent, /*requireStringLiteralLikeArgument*/ false) && node.parent.arguments[0] === node ||
2026            isImportCall(node.parent) && node.parent.arguments[0] === node);
2027    }
2028
2029    export type ObjectBindingElementWithoutPropertyName = BindingElement & { name: Identifier };
2030
2031    export function isObjectBindingElementWithoutPropertyName(bindingElement: Node): bindingElement is ObjectBindingElementWithoutPropertyName {
2032        return isBindingElement(bindingElement) &&
2033            isObjectBindingPattern(bindingElement.parent) &&
2034            isIdentifier(bindingElement.name) &&
2035            !bindingElement.propertyName;
2036    }
2037
2038    export function getPropertySymbolFromBindingElement(checker: TypeChecker, bindingElement: ObjectBindingElementWithoutPropertyName): Symbol | undefined {
2039        const typeOfPattern = checker.getTypeAtLocation(bindingElement.parent);
2040        return typeOfPattern && checker.getPropertyOfType(typeOfPattern, bindingElement.name.text);
2041    }
2042
2043    export function getParentNodeInSpan(node: Node | undefined, file: SourceFile, span: TextSpan): Node | undefined {
2044        if (!node) return undefined;
2045
2046        while (node.parent) {
2047            if (isSourceFile(node.parent) || !spanContainsNode(span, node.parent, file)) {
2048                return node;
2049            }
2050
2051            node = node.parent;
2052        }
2053    }
2054
2055    function spanContainsNode(span: TextSpan, node: Node, file: SourceFile): boolean {
2056        return textSpanContainsPosition(span, node.getStart(file)) &&
2057            node.getEnd() <= textSpanEnd(span);
2058    }
2059
2060    export function findModifier(node: Node, kind: Modifier["kind"]): Modifier | undefined {
2061        return canHaveModifiers(node) ? find(node.modifiers, (m): m is Modifier => m.kind === kind) : undefined;
2062    }
2063
2064    export function insertImports(changes: textChanges.ChangeTracker, sourceFile: SourceFile, imports: AnyImportOrRequireStatement | readonly AnyImportOrRequireStatement[], blankLineBetween: boolean): void {
2065        const decl = isArray(imports) ? imports[0] : imports;
2066        const importKindPredicate: (node: Node) => node is AnyImportOrRequireStatement = decl.kind === SyntaxKind.VariableStatement ? isRequireVariableStatement : isAnyImportSyntax;
2067        const existingImportStatements = filter(sourceFile.statements, importKindPredicate);
2068        const sortedNewImports = isArray(imports) ? stableSort(imports, OrganizeImports.compareImportsOrRequireStatements) : [imports];
2069        if (!existingImportStatements.length) {
2070            changes.insertNodesAtTopOfFile(sourceFile, sortedNewImports, blankLineBetween);
2071        }
2072        else if (existingImportStatements && OrganizeImports.importsAreSorted(existingImportStatements)) {
2073            for (const newImport of sortedNewImports) {
2074                const insertionIndex = OrganizeImports.getImportDeclarationInsertionIndex(existingImportStatements, newImport);
2075                if (insertionIndex === 0) {
2076                    // If the first import is top-of-file, insert after the leading comment which is likely the header.
2077                    const options = existingImportStatements[0] === sourceFile.statements[0] ?
2078                    { leadingTriviaOption: textChanges.LeadingTriviaOption.Exclude } : {};
2079                    changes.insertNodeBefore(sourceFile, existingImportStatements[0], newImport, /*blankLineBetween*/ false, options);
2080                }
2081                else {
2082                    const prevImport = existingImportStatements[insertionIndex - 1];
2083                    changes.insertNodeAfter(sourceFile, prevImport, newImport);
2084                }
2085            }
2086        }
2087        else {
2088            const lastExistingImport = lastOrUndefined(existingImportStatements);
2089            if (lastExistingImport) {
2090                changes.insertNodesAfter(sourceFile, lastExistingImport, sortedNewImports);
2091            }
2092            else {
2093                changes.insertNodesAtTopOfFile(sourceFile, sortedNewImports, blankLineBetween);
2094            }
2095        }
2096    }
2097
2098    export function getTypeKeywordOfTypeOnlyImport(importClause: ImportClause, sourceFile: SourceFile): Token<SyntaxKind.TypeKeyword> {
2099        Debug.assert(importClause.isTypeOnly);
2100        return cast(importClause.getChildAt(0, sourceFile), isTypeKeywordToken);
2101    }
2102
2103    export function textSpansEqual(a: TextSpan | undefined, b: TextSpan | undefined): boolean {
2104        return !!a && !!b && a.start === b.start && a.length === b.length;
2105    }
2106    export function documentSpansEqual(a: DocumentSpan, b: DocumentSpan): boolean {
2107        return a.fileName === b.fileName && textSpansEqual(a.textSpan, b.textSpan);
2108    }
2109
2110    /**
2111     * Iterates through 'array' by index and performs the callback on each element of array until the callback
2112     * returns a truthy value, then returns that value.
2113     * If no such value is found, the callback is applied to each element of array and undefined is returned.
2114     */
2115    export function forEachUnique<T, U>(array: readonly T[] | undefined, callback: (element: T, index: number) => U): U | undefined {
2116        if (array) {
2117            for (let i = 0; i < array.length; i++) {
2118                if (array.indexOf(array[i]) === i) {
2119                    const result = callback(array[i], i);
2120                    if (result) {
2121                        return result;
2122                    }
2123                }
2124            }
2125        }
2126        return undefined;
2127    }
2128
2129    export function isTextWhiteSpaceLike(text: string, startPos: number, endPos: number): boolean {
2130        for (let i = startPos; i < endPos; i++) {
2131            if (!isWhiteSpaceLike(text.charCodeAt(i))) {
2132                return false;
2133            }
2134        }
2135
2136        return true;
2137    }
2138
2139    export function getMappedLocation(location: DocumentPosition, sourceMapper: SourceMapper, fileExists: ((path: string) => boolean) | undefined): DocumentPosition | undefined {
2140        const mapsTo = sourceMapper.tryGetSourcePosition(location);
2141        return mapsTo && (!fileExists || fileExists(normalizePath(mapsTo.fileName)) ? mapsTo : undefined);
2142    }
2143
2144    export function getMappedDocumentSpan(documentSpan: DocumentSpan, sourceMapper: SourceMapper, fileExists?: (path: string) => boolean): DocumentSpan | undefined {
2145        const { fileName, textSpan } = documentSpan;
2146        const newPosition = getMappedLocation({ fileName, pos: textSpan.start }, sourceMapper, fileExists);
2147        if (!newPosition) return undefined;
2148        const newEndPosition = getMappedLocation({ fileName, pos: textSpan.start + textSpan.length }, sourceMapper, fileExists);
2149        const newLength = newEndPosition
2150            ? newEndPosition.pos - newPosition.pos
2151            : textSpan.length; // This shouldn't happen
2152        return {
2153            fileName: newPosition.fileName,
2154            textSpan: {
2155                start: newPosition.pos,
2156                length: newLength,
2157            },
2158            originalFileName: documentSpan.fileName,
2159            originalTextSpan: documentSpan.textSpan,
2160            contextSpan: getMappedContextSpan(documentSpan, sourceMapper, fileExists),
2161            originalContextSpan: documentSpan.contextSpan
2162        };
2163    }
2164
2165    export function getMappedContextSpan(documentSpan: DocumentSpan, sourceMapper: SourceMapper, fileExists?: (path: string) => boolean): TextSpan | undefined {
2166        const contextSpanStart = documentSpan.contextSpan && getMappedLocation(
2167            { fileName: documentSpan.fileName, pos: documentSpan.contextSpan.start },
2168            sourceMapper,
2169            fileExists
2170        );
2171        const contextSpanEnd = documentSpan.contextSpan && getMappedLocation(
2172            { fileName: documentSpan.fileName, pos: documentSpan.contextSpan.start + documentSpan.contextSpan.length },
2173            sourceMapper,
2174            fileExists
2175        );
2176        return contextSpanStart && contextSpanEnd ?
2177            { start: contextSpanStart.pos, length: contextSpanEnd.pos - contextSpanStart.pos } :
2178            undefined;
2179    }
2180
2181    // #endregion
2182
2183    // Display-part writer helpers
2184    // #region
2185    export function isFirstDeclarationOfSymbolParameter(symbol: Symbol) {
2186        const declaration = symbol.declarations ? firstOrUndefined(symbol.declarations) : undefined;
2187        return !!findAncestor(declaration, n =>
2188            isParameter(n) ? true : isBindingElement(n) || isObjectBindingPattern(n) || isArrayBindingPattern(n) ? false : "quit");
2189    }
2190
2191    const displayPartWriter = getDisplayPartWriter();
2192    function getDisplayPartWriter(): DisplayPartsSymbolWriter {
2193        const absoluteMaximumLength = defaultMaximumTruncationLength * 10; // A hard cutoff to avoid overloading the messaging channel in worst-case scenarios
2194        let displayParts: SymbolDisplayPart[];
2195        let lineStart: boolean;
2196        let indent: number;
2197        let length: number;
2198
2199        resetWriter();
2200        const unknownWrite = (text: string) => writeKind(text, SymbolDisplayPartKind.text);
2201        return {
2202            displayParts: () => {
2203                const finalText = displayParts.length && displayParts[displayParts.length - 1].text;
2204                if (length > absoluteMaximumLength && finalText && finalText !== "...") {
2205                    if (!isWhiteSpaceLike(finalText.charCodeAt(finalText.length - 1))) {
2206                        displayParts.push(displayPart(" ", SymbolDisplayPartKind.space));
2207                    }
2208                    displayParts.push(displayPart("...", SymbolDisplayPartKind.punctuation));
2209                }
2210                return displayParts;
2211            },
2212            writeKeyword: text => writeKind(text, SymbolDisplayPartKind.keyword),
2213            writeOperator: text => writeKind(text, SymbolDisplayPartKind.operator),
2214            writePunctuation: text => writeKind(text, SymbolDisplayPartKind.punctuation),
2215            writeTrailingSemicolon: text => writeKind(text, SymbolDisplayPartKind.punctuation),
2216            writeSpace: text => writeKind(text, SymbolDisplayPartKind.space),
2217            writeStringLiteral: text => writeKind(text, SymbolDisplayPartKind.stringLiteral),
2218            writeParameter: text => writeKind(text, SymbolDisplayPartKind.parameterName),
2219            writeProperty: text => writeKind(text, SymbolDisplayPartKind.propertyName),
2220            writeLiteral: text => writeKind(text, SymbolDisplayPartKind.stringLiteral),
2221            writeSymbol,
2222            writeLine,
2223            write: unknownWrite,
2224            writeComment: unknownWrite,
2225            getText: () => "",
2226            getTextPos: () => 0,
2227            getColumn: () => 0,
2228            getLine: () => 0,
2229            isAtStartOfLine: () => false,
2230            hasTrailingWhitespace: () => false,
2231            hasTrailingComment: () => false,
2232            rawWrite: notImplemented,
2233            getIndent: () => indent,
2234            increaseIndent: () => { indent++; },
2235            decreaseIndent: () => { indent--; },
2236            clear: resetWriter,
2237            trackSymbol: () => false,
2238            reportInaccessibleThisError: noop,
2239            reportInaccessibleUniqueSymbolError: noop,
2240            reportPrivateInBaseOfClassExpression: noop,
2241        };
2242
2243        function writeIndent() {
2244            if (length > absoluteMaximumLength) return;
2245            if (lineStart) {
2246                const indentString = getIndentString(indent);
2247                if (indentString) {
2248                    length += indentString.length;
2249                    displayParts.push(displayPart(indentString, SymbolDisplayPartKind.space));
2250                }
2251                lineStart = false;
2252            }
2253        }
2254
2255        function writeKind(text: string, kind: SymbolDisplayPartKind) {
2256            if (length > absoluteMaximumLength) return;
2257            writeIndent();
2258            length += text.length;
2259            displayParts.push(displayPart(text, kind));
2260        }
2261
2262        function writeSymbol(text: string, symbol: Symbol) {
2263            if (length > absoluteMaximumLength) return;
2264            writeIndent();
2265            length += text.length;
2266            displayParts.push(symbolPart(text, symbol));
2267        }
2268
2269        function writeLine() {
2270            if (length > absoluteMaximumLength) return;
2271            length += 1;
2272            displayParts.push(lineBreakPart());
2273            lineStart = true;
2274        }
2275
2276        function resetWriter() {
2277            displayParts = [];
2278            lineStart = true;
2279            indent = 0;
2280            length = 0;
2281        }
2282    }
2283
2284    export function symbolPart(text: string, symbol: Symbol) {
2285        return displayPart(text, displayPartKind(symbol));
2286
2287        function displayPartKind(symbol: Symbol): SymbolDisplayPartKind {
2288            const flags = symbol.flags;
2289
2290            if (flags & SymbolFlags.Variable) {
2291                return isFirstDeclarationOfSymbolParameter(symbol) ? SymbolDisplayPartKind.parameterName : SymbolDisplayPartKind.localName;
2292            }
2293            if (flags & SymbolFlags.Property) return SymbolDisplayPartKind.propertyName;
2294            if (flags & SymbolFlags.GetAccessor) return SymbolDisplayPartKind.propertyName;
2295            if (flags & SymbolFlags.SetAccessor) return SymbolDisplayPartKind.propertyName;
2296            if (flags & SymbolFlags.EnumMember) return SymbolDisplayPartKind.enumMemberName;
2297            if (flags & SymbolFlags.Function) return SymbolDisplayPartKind.functionName;
2298            if (flags & SymbolFlags.Class) return SymbolDisplayPartKind.className;
2299            if (flags & SymbolFlags.Interface) return SymbolDisplayPartKind.interfaceName;
2300            if (flags & SymbolFlags.Enum) return SymbolDisplayPartKind.enumName;
2301            if (flags & SymbolFlags.Module) return SymbolDisplayPartKind.moduleName;
2302            if (flags & SymbolFlags.Method) return SymbolDisplayPartKind.methodName;
2303            if (flags & SymbolFlags.TypeParameter) return SymbolDisplayPartKind.typeParameterName;
2304            if (flags & SymbolFlags.TypeAlias) return SymbolDisplayPartKind.aliasName;
2305            if (flags & SymbolFlags.Alias) return SymbolDisplayPartKind.aliasName;
2306
2307            return SymbolDisplayPartKind.text;
2308        }
2309    }
2310
2311    export function displayPart(text: string, kind: SymbolDisplayPartKind): SymbolDisplayPart {
2312        return { text, kind: SymbolDisplayPartKind[kind] };
2313    }
2314
2315    export function spacePart() {
2316        return displayPart(" ", SymbolDisplayPartKind.space);
2317    }
2318
2319    export function keywordPart(kind: SyntaxKind) {
2320        return displayPart(tokenToString(kind)!, SymbolDisplayPartKind.keyword);
2321    }
2322
2323    export function punctuationPart(kind: SyntaxKind) {
2324        return displayPart(tokenToString(kind)!, SymbolDisplayPartKind.punctuation);
2325    }
2326
2327    export function operatorPart(kind: SyntaxKind) {
2328        return displayPart(tokenToString(kind)!, SymbolDisplayPartKind.operator);
2329    }
2330
2331    export function parameterNamePart(text: string) {
2332        return displayPart(text, SymbolDisplayPartKind.parameterName);
2333    }
2334
2335    export function propertyNamePart(text: string) {
2336        return displayPart(text, SymbolDisplayPartKind.propertyName);
2337    }
2338
2339    export function textOrKeywordPart(text: string) {
2340        const kind = stringToToken(text);
2341        return kind === undefined
2342            ? textPart(text)
2343            : keywordPart(kind);
2344    }
2345
2346    export function textPart(text: string) {
2347        return displayPart(text, SymbolDisplayPartKind.text);
2348    }
2349
2350    export function typeAliasNamePart(text: string) {
2351        return displayPart(text, SymbolDisplayPartKind.aliasName);
2352    }
2353
2354    export function typeParameterNamePart(text: string) {
2355        return displayPart(text, SymbolDisplayPartKind.typeParameterName);
2356    }
2357
2358    export function linkTextPart(text: string) {
2359        return displayPart(text, SymbolDisplayPartKind.linkText);
2360    }
2361
2362    export function linkNamePart(text: string, target: Declaration): JSDocLinkDisplayPart {
2363        return {
2364            text,
2365            kind: SymbolDisplayPartKind[SymbolDisplayPartKind.linkName],
2366            target: {
2367                fileName: getSourceFileOfNode(target).fileName,
2368                textSpan: createTextSpanFromNode(target),
2369            },
2370        };
2371    }
2372
2373    export function linkPart(text: string) {
2374        return displayPart(text, SymbolDisplayPartKind.link);
2375    }
2376
2377    export function buildLinkParts(link: JSDocLink | JSDocLinkCode | JSDocLinkPlain, checker?: TypeChecker): SymbolDisplayPart[] {
2378        const prefix = isJSDocLink(link) ? "link"
2379            : isJSDocLinkCode(link) ? "linkcode"
2380            : "linkplain";
2381        const parts = [linkPart(`{@${prefix} `)];
2382        if (!link.name) {
2383            if (link.text) {
2384                parts.push(linkTextPart(link.text));
2385            }
2386        }
2387        else {
2388            const symbol = checker?.getSymbolAtLocation(link.name);
2389            const suffix = findLinkNameEnd(link.text);
2390            const name = getTextOfNode(link.name) + link.text.slice(0, suffix);
2391            const text = skipSeparatorFromLinkText(link.text.slice(suffix));
2392            const decl = symbol?.valueDeclaration || symbol?.declarations?.[0];
2393            if (decl) {
2394                parts.push(linkNamePart(name, decl));
2395                if (text) parts.push(linkTextPart(text));
2396            }
2397            else {
2398                parts.push(linkTextPart(name + (suffix || text.indexOf("://") === 0 ? "" : " ") + text));
2399            }
2400        }
2401        parts.push(linkPart("}"));
2402        return parts;
2403    }
2404
2405    function skipSeparatorFromLinkText(text: string) {
2406        let pos = 0;
2407        if (text.charCodeAt(pos++) === CharacterCodes.bar) {
2408            while (pos < text.length && text.charCodeAt(pos) === CharacterCodes.space) pos++;
2409            return text.slice(pos);
2410        }
2411        return text;
2412    }
2413
2414    function findLinkNameEnd(text: string) {
2415        if (text.indexOf("()") === 0) return 2;
2416        if (text[0] !== "<") return 0;
2417        let brackets = 0;
2418        let i = 0;
2419        while (i < text.length) {
2420            if (text[i] === "<") brackets++;
2421            if (text[i] === ">") brackets--;
2422            i++;
2423            if (!brackets) return i;
2424        }
2425        return 0;
2426    }
2427
2428    const carriageReturnLineFeed = "\r\n";
2429    /**
2430     * The default is CRLF.
2431     */
2432    export function getNewLineOrDefaultFromHost(host: FormattingHost, formatSettings?: FormatCodeSettings) {
2433        return formatSettings?.newLineCharacter ||
2434            host.getNewLine?.() ||
2435            carriageReturnLineFeed;
2436    }
2437
2438    export function lineBreakPart() {
2439        return displayPart("\n", SymbolDisplayPartKind.lineBreak);
2440    }
2441
2442    export function mapToDisplayParts(writeDisplayParts: (writer: DisplayPartsSymbolWriter) => void): SymbolDisplayPart[] {
2443        try {
2444            writeDisplayParts(displayPartWriter);
2445            return displayPartWriter.displayParts();
2446        }
2447        finally {
2448            displayPartWriter.clear();
2449        }
2450    }
2451
2452    export function typeToDisplayParts(typechecker: TypeChecker, type: Type, enclosingDeclaration?: Node, flags: TypeFormatFlags = TypeFormatFlags.None): SymbolDisplayPart[] {
2453        return mapToDisplayParts(writer => {
2454            typechecker.writeType(type, enclosingDeclaration, flags | TypeFormatFlags.MultilineObjectLiterals | TypeFormatFlags.UseAliasDefinedOutsideCurrentScope, writer);
2455        });
2456    }
2457
2458    export function symbolToDisplayParts(typeChecker: TypeChecker, symbol: Symbol, enclosingDeclaration?: Node, meaning?: SymbolFlags, flags: SymbolFormatFlags = SymbolFormatFlags.None): SymbolDisplayPart[] {
2459        return mapToDisplayParts(writer => {
2460            typeChecker.writeSymbol(symbol, enclosingDeclaration, meaning, flags | SymbolFormatFlags.UseAliasDefinedOutsideCurrentScope, writer);
2461        });
2462    }
2463
2464    export function signatureToDisplayParts(typechecker: TypeChecker, signature: Signature, enclosingDeclaration?: Node, flags: TypeFormatFlags = TypeFormatFlags.None): SymbolDisplayPart[] {
2465        flags |= TypeFormatFlags.UseAliasDefinedOutsideCurrentScope | TypeFormatFlags.MultilineObjectLiterals | TypeFormatFlags.WriteTypeArgumentsOfSignature | TypeFormatFlags.OmitParameterModifiers;
2466        return mapToDisplayParts(writer => {
2467            typechecker.writeSignature(signature, enclosingDeclaration, flags, /*signatureKind*/ undefined, writer);
2468        });
2469    }
2470
2471    export function nodeToDisplayParts(node: Node, enclosingDeclaration: Node): SymbolDisplayPart[] {
2472        const file = enclosingDeclaration.getSourceFile();
2473        return mapToDisplayParts(writer => {
2474            const printer = createPrinter({ removeComments: true, omitTrailingSemicolon: true });
2475            printer.writeNode(EmitHint.Unspecified, node, file, writer);
2476        });
2477    }
2478
2479    export function isImportOrExportSpecifierName(location: Node): location is Identifier {
2480        return !!location.parent && isImportOrExportSpecifier(location.parent) && location.parent.propertyName === location;
2481    }
2482
2483    export function getScriptKind(fileName: string, host: LanguageServiceHost): ScriptKind {
2484        // First check to see if the script kind was specified by the host. Chances are the host
2485        // may override the default script kind for the file extension.
2486        return ensureScriptKind(fileName, host.getScriptKind && host.getScriptKind(fileName));
2487    }
2488
2489    export function getSymbolTarget(symbol: Symbol, checker: TypeChecker): Symbol {
2490        let next: Symbol = symbol;
2491        while (isAliasSymbol(next) || (isTransientSymbol(next) && next.target)) {
2492            if (isTransientSymbol(next) && next.target) {
2493                next = next.target;
2494            }
2495            else {
2496                next = skipAlias(next, checker);
2497            }
2498        }
2499        return next;
2500    }
2501
2502    function isTransientSymbol(symbol: Symbol): symbol is TransientSymbol {
2503        return (symbol.flags & SymbolFlags.Transient) !== 0;
2504    }
2505
2506    function isAliasSymbol(symbol: Symbol): boolean {
2507        return (symbol.flags & SymbolFlags.Alias) !== 0;
2508    }
2509
2510    export function getUniqueSymbolId(symbol: Symbol, checker: TypeChecker) {
2511        return getSymbolId(skipAlias(symbol, checker));
2512    }
2513
2514    export function getFirstNonSpaceCharacterPosition(text: string, position: number) {
2515        while (isWhiteSpaceLike(text.charCodeAt(position))) {
2516            position += 1;
2517        }
2518        return position;
2519    }
2520
2521    export function getPrecedingNonSpaceCharacterPosition(text: string, position: number) {
2522        while (position > -1 && isWhiteSpaceSingleLine(text.charCodeAt(position))) {
2523            position -= 1;
2524        }
2525        return position + 1;
2526    }
2527
2528    /**
2529     * Creates a deep, memberwise clone of a node with no source map location.
2530     *
2531     * WARNING: This is an expensive operation and is only intended to be used in refactorings
2532     * and code fixes (because those are triggered by explicit user actions).
2533     */
2534    export function getSynthesizedDeepClone<T extends Node | undefined>(node: T, includeTrivia = true): T {
2535        const clone = node && getSynthesizedDeepCloneWorker(node);
2536        if (clone && !includeTrivia) suppressLeadingAndTrailingTrivia(clone);
2537        return clone;
2538    }
2539
2540    export function getSynthesizedDeepCloneWithReplacements<T extends Node>(
2541        node: T,
2542        includeTrivia: boolean,
2543        replaceNode: (node: Node) => Node | undefined
2544    ): T {
2545        let clone = replaceNode(node);
2546        if (clone) {
2547            setOriginalNode(clone, node);
2548        }
2549        else {
2550            clone = getSynthesizedDeepCloneWorker(node as NonNullable<T>, replaceNode);
2551        }
2552
2553        if (clone && !includeTrivia) suppressLeadingAndTrailingTrivia(clone);
2554        return clone as T;
2555    }
2556
2557    function getSynthesizedDeepCloneWorker<T extends Node>(node: T, replaceNode?: (node: Node) => Node | undefined): T {
2558        const nodeClone: (n: T) => T = replaceNode
2559            ? n => getSynthesizedDeepCloneWithReplacements(n, /*includeTrivia*/ true, replaceNode)
2560            : getSynthesizedDeepClone;
2561        const nodesClone: (ns: NodeArray<T>) => NodeArray<T> = replaceNode
2562            ? ns => ns && getSynthesizedDeepClonesWithReplacements(ns, /*includeTrivia*/ true, replaceNode)
2563            : ns => ns && getSynthesizedDeepClones(ns);
2564        const visited =
2565            visitEachChild(node, nodeClone, nullTransformationContext, nodesClone, nodeClone);
2566
2567        if (visited === node) {
2568            // This only happens for leaf nodes - internal nodes always see their children change.
2569            const clone =
2570                isStringLiteral(node) ? setOriginalNode(factory.createStringLiteralFromNode(node), node) as Node as T :
2571                    isNumericLiteral(node) ? setOriginalNode(factory.createNumericLiteral(node.text, node.numericLiteralFlags), node) as Node as T :
2572                        factory.cloneNode(node);
2573            return setTextRange(clone, node);
2574        }
2575
2576        // PERF: As an optimization, rather than calling factory.cloneNode, we'll update
2577        // the new node created by visitEachChild with the extra changes factory.cloneNode
2578        // would have made.
2579        (visited as Mutable<T>).parent = undefined!;
2580        return visited;
2581    }
2582
2583    export function getSynthesizedDeepClones<T extends Node>(nodes: NodeArray<T>, includeTrivia?: boolean): NodeArray<T>;
2584    export function getSynthesizedDeepClones<T extends Node>(nodes: NodeArray<T> | undefined, includeTrivia?: boolean): NodeArray<T> | undefined;
2585    export function getSynthesizedDeepClones<T extends Node>(nodes: NodeArray<T> | undefined, includeTrivia = true): NodeArray<T> | undefined {
2586        return nodes && factory.createNodeArray(nodes.map(n => getSynthesizedDeepClone(n, includeTrivia)), nodes.hasTrailingComma);
2587    }
2588
2589    export function getSynthesizedDeepClonesWithReplacements<T extends Node>(
2590        nodes: NodeArray<T>,
2591        includeTrivia: boolean,
2592        replaceNode: (node: Node) => Node | undefined
2593    ): NodeArray<T> {
2594        return factory.createNodeArray(nodes.map(n => getSynthesizedDeepCloneWithReplacements(n, includeTrivia, replaceNode)), nodes.hasTrailingComma);
2595    }
2596
2597    /**
2598     * Sets EmitFlags to suppress leading and trailing trivia on the node.
2599     */
2600    export function suppressLeadingAndTrailingTrivia(node: Node) {
2601        suppressLeadingTrivia(node);
2602        suppressTrailingTrivia(node);
2603    }
2604
2605    /**
2606     * Sets EmitFlags to suppress leading trivia on the node.
2607     */
2608    export function suppressLeadingTrivia(node: Node) {
2609        addEmitFlagsRecursively(node, EmitFlags.NoLeadingComments, getFirstChild);
2610    }
2611
2612    /**
2613     * Sets EmitFlags to suppress trailing trivia on the node.
2614     */
2615    export function suppressTrailingTrivia(node: Node) {
2616        addEmitFlagsRecursively(node, EmitFlags.NoTrailingComments, getLastChild);
2617    }
2618
2619    export function copyComments(sourceNode: Node, targetNode: Node) {
2620        const sourceFile = sourceNode.getSourceFile();
2621        const text = sourceFile.text;
2622        if (hasLeadingLineBreak(sourceNode, text)) {
2623            copyLeadingComments(sourceNode, targetNode, sourceFile);
2624        }
2625        else {
2626            copyTrailingAsLeadingComments(sourceNode, targetNode, sourceFile);
2627        }
2628        copyTrailingComments(sourceNode, targetNode, sourceFile);
2629    }
2630
2631    function hasLeadingLineBreak(node: Node, text: string) {
2632        const start = node.getFullStart();
2633        const end = node.getStart();
2634        for (let i = start; i < end; i++) {
2635            if (text.charCodeAt(i) === CharacterCodes.lineFeed) return true;
2636        }
2637        return false;
2638    }
2639
2640    function addEmitFlagsRecursively(node: Node, flag: EmitFlags, getChild: (n: Node) => Node | undefined) {
2641        addEmitFlags(node, flag);
2642        const child = getChild(node);
2643        if (child) addEmitFlagsRecursively(child, flag, getChild);
2644    }
2645
2646    function getFirstChild(node: Node): Node | undefined {
2647        return node.forEachChild(child => child);
2648    }
2649
2650    export function getUniqueName(baseName: string, sourceFile: SourceFile): string {
2651        let nameText = baseName;
2652        for (let i = 1; !isFileLevelUniqueName(sourceFile, nameText); i++) {
2653            nameText = `${baseName}_${i}`;
2654        }
2655        return nameText;
2656    }
2657
2658    /**
2659     * @return The index of the (only) reference to the extracted symbol.  We want the cursor
2660     * to be on the reference, rather than the declaration, because it's closer to where the
2661     * user was before extracting it.
2662     */
2663    export function getRenameLocation(edits: readonly FileTextChanges[], renameFilename: string, name: string, preferLastLocation: boolean): number {
2664        let delta = 0;
2665        let lastPos = -1;
2666        for (const { fileName, textChanges } of edits) {
2667            Debug.assert(fileName === renameFilename);
2668            for (const change of textChanges) {
2669                const { span, newText } = change;
2670                const index = indexInTextChange(newText, escapeString(name));
2671                if (index !== -1) {
2672                    lastPos = span.start + delta + index;
2673
2674                    // If the reference comes first, return immediately.
2675                    if (!preferLastLocation) {
2676                        return lastPos;
2677                    }
2678                }
2679                delta += newText.length - span.length;
2680            }
2681        }
2682
2683        // If the declaration comes first, return the position of the last occurrence.
2684        Debug.assert(preferLastLocation);
2685        Debug.assert(lastPos >= 0);
2686        return lastPos;
2687    }
2688
2689    export function copyLeadingComments(sourceNode: Node, targetNode: Node, sourceFile: SourceFile, commentKind?: CommentKind, hasTrailingNewLine?: boolean) {
2690        forEachLeadingCommentRange(sourceFile.text, sourceNode.pos, getAddCommentsFunction(targetNode, sourceFile, commentKind, hasTrailingNewLine, addSyntheticLeadingComment));
2691    }
2692
2693
2694    export function copyTrailingComments(sourceNode: Node, targetNode: Node, sourceFile: SourceFile, commentKind?: CommentKind, hasTrailingNewLine?: boolean) {
2695        forEachTrailingCommentRange(sourceFile.text, sourceNode.end, getAddCommentsFunction(targetNode, sourceFile, commentKind, hasTrailingNewLine, addSyntheticTrailingComment));
2696    }
2697
2698    /**
2699     * This function copies the trailing comments for the token that comes before `sourceNode`, as leading comments of `targetNode`.
2700     * This is useful because sometimes a comment that refers to `sourceNode` will be a leading comment for `sourceNode`, according to the
2701     * notion of trivia ownership, and instead will be a trailing comment for the token before `sourceNode`, e.g.:
2702     * `function foo(\* not leading comment for a *\ a: string) {}`
2703     * The comment refers to `a` but belongs to the `(` token, but we might want to copy it.
2704     */
2705    export function copyTrailingAsLeadingComments(sourceNode: Node, targetNode: Node, sourceFile: SourceFile, commentKind?: CommentKind, hasTrailingNewLine?: boolean) {
2706        forEachTrailingCommentRange(sourceFile.text, sourceNode.pos, getAddCommentsFunction(targetNode, sourceFile, commentKind, hasTrailingNewLine, addSyntheticLeadingComment));
2707    }
2708
2709    function getAddCommentsFunction(targetNode: Node, sourceFile: SourceFile, commentKind: CommentKind | undefined, hasTrailingNewLine: boolean | undefined, cb: (node: Node, kind: CommentKind, text: string, hasTrailingNewLine?: boolean) => void) {
2710        return (pos: number, end: number, kind: CommentKind, htnl: boolean) => {
2711            if (kind === SyntaxKind.MultiLineCommentTrivia) {
2712                // Remove leading /*
2713                pos += 2;
2714                // Remove trailing */
2715                end -= 2;
2716            }
2717            else {
2718                // Remove leading //
2719                pos += 2;
2720            }
2721            cb(targetNode, commentKind || kind, sourceFile.text.slice(pos, end), hasTrailingNewLine !== undefined ? hasTrailingNewLine : htnl);
2722        };
2723    }
2724
2725    function indexInTextChange(change: string, name: string): number {
2726        if (startsWith(change, name)) return 0;
2727        // Add a " " to avoid references inside words
2728        let idx = change.indexOf(" " + name);
2729        if (idx === -1) idx = change.indexOf("." + name);
2730        if (idx === -1) idx = change.indexOf('"' + name);
2731        return idx === -1 ? -1 : idx + 1;
2732    }
2733
2734    /* @internal */
2735    export function needsParentheses(expression: Expression): boolean {
2736        return isBinaryExpression(expression) && expression.operatorToken.kind === SyntaxKind.CommaToken
2737            || isObjectLiteralExpression(expression)
2738            || isAsExpression(expression) && isObjectLiteralExpression(expression.expression);
2739    }
2740
2741    export function getContextualTypeFromParent(node: Expression, checker: TypeChecker): Type | undefined {
2742        const { parent } = node;
2743        switch (parent.kind) {
2744            case SyntaxKind.NewExpression:
2745                return checker.getContextualType(parent as NewExpression);
2746            case SyntaxKind.BinaryExpression: {
2747                const { left, operatorToken, right } = parent as BinaryExpression;
2748                return isEqualityOperatorKind(operatorToken.kind)
2749                    ? checker.getTypeAtLocation(node === right ? left : right)
2750                    : checker.getContextualType(node);
2751            }
2752            case SyntaxKind.CaseClause:
2753                return (parent as CaseClause).expression === node ? getSwitchedType(parent as CaseClause, checker) : undefined;
2754            default:
2755                return checker.getContextualType(node);
2756        }
2757    }
2758
2759    export function quote(sourceFile: SourceFile, preferences: UserPreferences, text: string): string {
2760        // Editors can pass in undefined or empty string - we want to infer the preference in those cases.
2761        const quotePreference = getQuotePreference(sourceFile, preferences);
2762        const quoted = JSON.stringify(text);
2763        return quotePreference === QuotePreference.Single ? `'${stripQuotes(quoted).replace(/'/g, "\\'").replace(/\\"/g, '"')}'` : quoted;
2764    }
2765
2766    export function isEqualityOperatorKind(kind: SyntaxKind): kind is EqualityOperator {
2767        switch (kind) {
2768            case SyntaxKind.EqualsEqualsEqualsToken:
2769            case SyntaxKind.EqualsEqualsToken:
2770            case SyntaxKind.ExclamationEqualsEqualsToken:
2771            case SyntaxKind.ExclamationEqualsToken:
2772                return true;
2773            default:
2774                return false;
2775        }
2776    }
2777
2778    export function isStringLiteralOrTemplate(node: Node): node is StringLiteralLike | TemplateExpression | TaggedTemplateExpression {
2779        switch (node.kind) {
2780            case SyntaxKind.StringLiteral:
2781            case SyntaxKind.NoSubstitutionTemplateLiteral:
2782            case SyntaxKind.TemplateExpression:
2783            case SyntaxKind.TaggedTemplateExpression:
2784                return true;
2785            default:
2786                return false;
2787        }
2788    }
2789
2790    export function hasIndexSignature(type: Type): boolean {
2791        return !!type.getStringIndexType() || !!type.getNumberIndexType();
2792    }
2793
2794    export function getSwitchedType(caseClause: CaseClause, checker: TypeChecker): Type | undefined {
2795        return checker.getTypeAtLocation(caseClause.parent.parent.expression);
2796    }
2797
2798    export const ANONYMOUS = "anonymous function";
2799
2800    export function getTypeNodeIfAccessible(type: Type, enclosingScope: Node, program: Program, host: LanguageServiceHost): TypeNode | undefined {
2801        const checker = program.getTypeChecker();
2802        let typeIsAccessible = true;
2803        const notAccessible = () => typeIsAccessible = false;
2804        const res = checker.typeToTypeNode(type, enclosingScope, NodeBuilderFlags.NoTruncation, {
2805            trackSymbol: (symbol, declaration, meaning) => {
2806                typeIsAccessible = typeIsAccessible && checker.isSymbolAccessible(symbol, declaration, meaning, /*shouldComputeAliasToMarkVisible*/ false).accessibility === SymbolAccessibility.Accessible;
2807                return !typeIsAccessible;
2808            },
2809            reportInaccessibleThisError: notAccessible,
2810            reportPrivateInBaseOfClassExpression: notAccessible,
2811            reportInaccessibleUniqueSymbolError: notAccessible,
2812            moduleResolverHost: getModuleSpecifierResolverHost(program, host)
2813        });
2814        return typeIsAccessible ? res : undefined;
2815    }
2816
2817    function syntaxRequiresTrailingCommaOrSemicolonOrASI(kind: SyntaxKind) {
2818        return kind === SyntaxKind.CallSignature
2819            || kind === SyntaxKind.ConstructSignature
2820            || kind === SyntaxKind.IndexSignature
2821            || kind === SyntaxKind.PropertySignature
2822            || kind === SyntaxKind.MethodSignature;
2823    }
2824
2825    function syntaxRequiresTrailingFunctionBlockOrSemicolonOrASI(kind: SyntaxKind) {
2826        return kind === SyntaxKind.FunctionDeclaration
2827            || kind === SyntaxKind.Constructor
2828            || kind === SyntaxKind.MethodDeclaration
2829            || kind === SyntaxKind.GetAccessor
2830            || kind === SyntaxKind.SetAccessor;
2831    }
2832
2833    function syntaxRequiresTrailingModuleBlockOrSemicolonOrASI(kind: SyntaxKind) {
2834        return kind === SyntaxKind.ModuleDeclaration;
2835    }
2836
2837    export function syntaxRequiresTrailingSemicolonOrASI(kind: SyntaxKind) {
2838        return kind === SyntaxKind.VariableStatement
2839            || kind === SyntaxKind.ExpressionStatement
2840            || kind === SyntaxKind.DoStatement
2841            || kind === SyntaxKind.ContinueStatement
2842            || kind === SyntaxKind.BreakStatement
2843            || kind === SyntaxKind.ReturnStatement
2844            || kind === SyntaxKind.ThrowStatement
2845            || kind === SyntaxKind.DebuggerStatement
2846            || kind === SyntaxKind.PropertyDeclaration
2847            || kind === SyntaxKind.TypeAliasDeclaration
2848            || kind === SyntaxKind.ImportDeclaration
2849            || kind === SyntaxKind.ImportEqualsDeclaration
2850            || kind === SyntaxKind.ExportDeclaration
2851            || kind === SyntaxKind.NamespaceExportDeclaration
2852            || kind === SyntaxKind.ExportAssignment;
2853    }
2854
2855    export const syntaxMayBeASICandidate = or(
2856        syntaxRequiresTrailingCommaOrSemicolonOrASI,
2857        syntaxRequiresTrailingFunctionBlockOrSemicolonOrASI,
2858        syntaxRequiresTrailingModuleBlockOrSemicolonOrASI,
2859        syntaxRequiresTrailingSemicolonOrASI);
2860
2861    function nodeIsASICandidate(node: Node, sourceFile: SourceFileLike): boolean {
2862        const lastToken = node.getLastToken(sourceFile);
2863        if (lastToken && lastToken.kind === SyntaxKind.SemicolonToken) {
2864            return false;
2865        }
2866
2867        if (syntaxRequiresTrailingCommaOrSemicolonOrASI(node.kind)) {
2868            if (lastToken && lastToken.kind === SyntaxKind.CommaToken) {
2869                return false;
2870            }
2871        }
2872        else if (syntaxRequiresTrailingModuleBlockOrSemicolonOrASI(node.kind)) {
2873            const lastChild = last(node.getChildren(sourceFile));
2874            if (lastChild && isModuleBlock(lastChild)) {
2875                return false;
2876            }
2877        }
2878        else if (syntaxRequiresTrailingFunctionBlockOrSemicolonOrASI(node.kind)) {
2879            const lastChild = last(node.getChildren(sourceFile));
2880            if (lastChild && isFunctionBlock(lastChild)) {
2881                return false;
2882            }
2883        }
2884        else if (!syntaxRequiresTrailingSemicolonOrASI(node.kind)) {
2885            return false;
2886        }
2887
2888        // See comment in parser’s `parseDoStatement`
2889        if (node.kind === SyntaxKind.DoStatement) {
2890            return true;
2891        }
2892
2893        const topNode = findAncestor(node, ancestor => !ancestor.parent)!;
2894        const nextToken = findNextToken(node, topNode, sourceFile);
2895        if (!nextToken || nextToken.kind === SyntaxKind.CloseBraceToken) {
2896            return true;
2897        }
2898
2899        const startLine = sourceFile.getLineAndCharacterOfPosition(node.getEnd()).line;
2900        const endLine = sourceFile.getLineAndCharacterOfPosition(nextToken.getStart(sourceFile)).line;
2901        return startLine !== endLine;
2902    }
2903
2904    export function positionIsASICandidate(pos: number, context: Node, sourceFile: SourceFileLike): boolean {
2905        const contextAncestor = findAncestor(context, ancestor => {
2906            if (ancestor.end !== pos) {
2907                return "quit";
2908            }
2909            return syntaxMayBeASICandidate(ancestor.kind);
2910        });
2911
2912        return !!contextAncestor && nodeIsASICandidate(contextAncestor, sourceFile);
2913    }
2914
2915    export function probablyUsesSemicolons(sourceFile: SourceFile): boolean {
2916        let withSemicolon = 0;
2917        let withoutSemicolon = 0;
2918        const nStatementsToObserve = 5;
2919        forEachChild(sourceFile, function visit(node): boolean | undefined {
2920            if (syntaxRequiresTrailingSemicolonOrASI(node.kind)) {
2921                const lastToken = node.getLastToken(sourceFile);
2922                if (lastToken?.kind === SyntaxKind.SemicolonToken) {
2923                    withSemicolon++;
2924                }
2925                else {
2926                    withoutSemicolon++;
2927                }
2928            }
2929            else if (syntaxRequiresTrailingCommaOrSemicolonOrASI(node.kind)) {
2930                const lastToken = node.getLastToken(sourceFile);
2931                if (lastToken?.kind === SyntaxKind.SemicolonToken) {
2932                    withSemicolon++;
2933                }
2934                else if (lastToken && lastToken.kind !== SyntaxKind.CommaToken) {
2935                    const lastTokenLine = getLineAndCharacterOfPosition(sourceFile, lastToken.getStart(sourceFile)).line;
2936                    const nextTokenLine = getLineAndCharacterOfPosition(sourceFile, getSpanOfTokenAtPosition(sourceFile, lastToken.end).start).line;
2937                    // Avoid counting missing semicolon in single-line objects:
2938                    // `function f(p: { x: string /*no semicolon here is insignificant*/ }) {`
2939                    if (lastTokenLine !== nextTokenLine) {
2940                        withoutSemicolon++;
2941                    }
2942                }
2943            }
2944
2945            if (withSemicolon + withoutSemicolon >= nStatementsToObserve) {
2946                return true;
2947            }
2948
2949            return forEachChild(node, visit);
2950        });
2951
2952        // One statement missing a semicolon isn't sufficient evidence to say the user
2953        // doesn’t want semicolons, because they may not even be done writing that statement.
2954        if (withSemicolon === 0 && withoutSemicolon <= 1) {
2955            return true;
2956        }
2957
2958        // If even 2/5 places have a semicolon, the user probably wants semicolons
2959        return withSemicolon / withoutSemicolon > 1 / nStatementsToObserve;
2960    }
2961
2962    export function tryGetDirectories(host: Pick<LanguageServiceHost, "getDirectories">, directoryName: string): string[] {
2963        return tryIOAndConsumeErrors(host, host.getDirectories, directoryName) || [];
2964    }
2965
2966    export function tryReadDirectory(host: Pick<LanguageServiceHost, "readDirectory">, path: string, extensions?: readonly string[], exclude?: readonly string[], include?: readonly string[]): readonly string[] {
2967        return tryIOAndConsumeErrors(host, host.readDirectory, path, extensions, exclude, include) || emptyArray;
2968    }
2969
2970    export function tryFileExists(host: Pick<LanguageServiceHost, "fileExists">, path: string): boolean {
2971        return tryIOAndConsumeErrors(host, host.fileExists, path);
2972    }
2973
2974    export function tryDirectoryExists(host: LanguageServiceHost, path: string): boolean {
2975        return tryAndIgnoreErrors(() => directoryProbablyExists(path, host)) || false;
2976    }
2977
2978    export function tryAndIgnoreErrors<T>(cb: () => T): T | undefined {
2979        try {
2980            return cb();
2981        }
2982        catch {
2983            return undefined;
2984        }
2985    }
2986
2987    export function tryIOAndConsumeErrors<T>(host: unknown, toApply: ((...a: any[]) => T) | undefined, ...args: any[]) {
2988        return tryAndIgnoreErrors(() => toApply && toApply.apply(host, args));
2989    }
2990
2991    export function findPackageJsons(startDirectory: string, host: LanguageServiceHost, stopDirectory?: string): string[] {
2992        const paths: string[] = [];
2993        forEachAncestorDirectory(startDirectory, ancestor => {
2994            if (ancestor === stopDirectory) {
2995                return true;
2996            }
2997            const currentConfigPath = combinePaths(ancestor, getPackageJsonByPMType(host.getCompilationSettings().packageManagerType));
2998            if (tryFileExists(host, currentConfigPath)) {
2999                paths.push(currentConfigPath);
3000            }
3001        });
3002        return paths;
3003    }
3004
3005    export function findPackageJson(directory: string, host: LanguageServiceHost): string | undefined {
3006        let packageJson: string | undefined;
3007        forEachAncestorDirectory(directory, ancestor => {
3008            const moduleType: string = getModuleByPMType(host.getCompilationSettings().packageManagerType);
3009            const packageJsonType: string = getPackageJsonByPMType(host.getCompilationSettings().packageManagerType);
3010            if (ancestor === moduleType) return true;
3011            packageJson = findConfigFile(ancestor, (f) => tryFileExists(host, f), packageJsonType);
3012            if (packageJson) {
3013                return true; // break out
3014            }
3015        });
3016        return packageJson;
3017    }
3018
3019    export function getPackageJsonsVisibleToFile(fileName: string, host: LanguageServiceHost): readonly ProjectPackageJsonInfo[] {
3020        if (!host.fileExists) {
3021            return [];
3022        }
3023
3024        const packageJsons: ProjectPackageJsonInfo[] = [];
3025        forEachAncestorDirectory(getDirectoryPath(fileName), ancestor => {
3026            const packageJsonFileName = combinePaths(ancestor, getPackageJsonByPMType(host.getCompilationSettings().packageManagerType));
3027            if (host.fileExists(packageJsonFileName)) {
3028                const info = createPackageJsonInfo(packageJsonFileName, host);
3029                if (info) {
3030                    packageJsons.push(info);
3031                }
3032            }
3033        });
3034
3035        return packageJsons;
3036    }
3037
3038    export function createPackageJsonInfo(fileName: string, host: { readFile?(fileName: string): string | undefined }): ProjectPackageJsonInfo | undefined {
3039        if (!host.readFile) {
3040            return undefined;
3041        }
3042
3043        type PackageJsonRaw = Record<typeof dependencyKeys[number], Record<string, string> | undefined>;
3044        const dependencyKeys = ["dependencies", "devDependencies", "optionalDependencies", "peerDependencies"] as const;
3045        const stringContent = host.readFile(fileName) || "";
3046        const content = tryParseJson(stringContent) as PackageJsonRaw | undefined;
3047        const info: Pick<ProjectPackageJsonInfo, typeof dependencyKeys[number]> = {};
3048        if (content) {
3049            for (const key of dependencyKeys) {
3050                const dependencies = content[key];
3051                if (!dependencies) {
3052                    continue;
3053                }
3054                const dependencyMap = new Map<string, string>();
3055                for (const packageName in dependencies) {
3056                    dependencyMap.set(packageName, dependencies[packageName]);
3057                }
3058                info[key] = dependencyMap;
3059            }
3060        }
3061
3062        const dependencyGroups = [
3063            [PackageJsonDependencyGroup.Dependencies, info.dependencies],
3064            [PackageJsonDependencyGroup.DevDependencies, info.devDependencies],
3065            [PackageJsonDependencyGroup.OptionalDependencies, info.optionalDependencies],
3066            [PackageJsonDependencyGroup.PeerDependencies, info.peerDependencies],
3067        ] as const;
3068
3069        return {
3070            ...info,
3071            parseable: !!content,
3072            fileName,
3073            get,
3074            has(dependencyName, inGroups) {
3075                return !!get(dependencyName, inGroups);
3076            },
3077        };
3078
3079        function get(dependencyName: string, inGroups = PackageJsonDependencyGroup.All) {
3080            for (const [group, deps] of dependencyGroups) {
3081                if (deps && (inGroups & group)) {
3082                    const dep = deps.get(dependencyName);
3083                    if (dep !== undefined) {
3084                        return dep;
3085                    }
3086                }
3087            }
3088        }
3089    }
3090
3091    export interface PackageJsonImportFilter {
3092        allowsImportingAmbientModule: (moduleSymbol: Symbol, moduleSpecifierResolutionHost: ModuleSpecifierResolutionHost) => boolean;
3093        allowsImportingSourceFile: (sourceFile: SourceFile, moduleSpecifierResolutionHost: ModuleSpecifierResolutionHost) => boolean;
3094        /**
3095         * Use for a specific module specifier that has already been resolved.
3096         * Use `allowsImportingAmbientModule` or `allowsImportingSourceFile` to resolve
3097         * the best module specifier for a given module _and_ determine if it’s importable.
3098         */
3099        allowsImportingSpecifier: (moduleSpecifier: string) => boolean;
3100    }
3101
3102    export function createPackageJsonImportFilter(fromFile: SourceFile, preferences: UserPreferences, host: LanguageServiceHost): PackageJsonImportFilter {
3103        const packageJsons = (
3104            (host.getPackageJsonsVisibleToFile && host.getPackageJsonsVisibleToFile(fromFile.fileName)) || getPackageJsonsVisibleToFile(fromFile.fileName, host)
3105          ).filter(p => p.parseable);
3106
3107        let usesNodeCoreModules: boolean | undefined;
3108        return { allowsImportingAmbientModule, allowsImportingSourceFile, allowsImportingSpecifier };
3109
3110        function moduleSpecifierIsCoveredByPackageJson(specifier: string) {
3111            const packageName = getNodeModuleRootSpecifier(specifier);
3112            for (const packageJson of packageJsons) {
3113                if (packageJson.has(packageName) || packageJson.has(getTypesPackageName(packageName))) {
3114                    return true;
3115                }
3116            }
3117            return false;
3118        }
3119
3120        function allowsImportingAmbientModule(moduleSymbol: Symbol, moduleSpecifierResolutionHost: ModuleSpecifierResolutionHost): boolean {
3121            if (!packageJsons.length || !moduleSymbol.valueDeclaration) {
3122                return true;
3123            }
3124
3125            const declaringSourceFile = moduleSymbol.valueDeclaration.getSourceFile();
3126            const declaringNodeModuleName = getNodeModulesPackageNameFromFileName(declaringSourceFile.fileName, moduleSpecifierResolutionHost);
3127            if (typeof declaringNodeModuleName === "undefined") {
3128                return true;
3129            }
3130
3131            const declaredModuleSpecifier = stripQuotes(moduleSymbol.getName());
3132            if (isAllowedCoreNodeModulesImport(declaredModuleSpecifier)) {
3133                return true;
3134            }
3135
3136            return moduleSpecifierIsCoveredByPackageJson(declaringNodeModuleName)
3137                || moduleSpecifierIsCoveredByPackageJson(declaredModuleSpecifier);
3138        }
3139
3140        function allowsImportingSourceFile(sourceFile: SourceFile, moduleSpecifierResolutionHost: ModuleSpecifierResolutionHost): boolean {
3141            if (!packageJsons.length) {
3142                return true;
3143            }
3144
3145            const moduleSpecifier = getNodeModulesPackageNameFromFileName(sourceFile.fileName, moduleSpecifierResolutionHost);
3146            if (!moduleSpecifier) {
3147                return true;
3148            }
3149
3150            return moduleSpecifierIsCoveredByPackageJson(moduleSpecifier);
3151        }
3152
3153        function allowsImportingSpecifier(moduleSpecifier: string) {
3154            if (!packageJsons.length || isAllowedCoreNodeModulesImport(moduleSpecifier)) {
3155                return true;
3156            }
3157            if (pathIsRelative(moduleSpecifier) || isRootedDiskPath(moduleSpecifier)) {
3158                return true;
3159            }
3160            return moduleSpecifierIsCoveredByPackageJson(moduleSpecifier);
3161        }
3162
3163        function isAllowedCoreNodeModulesImport(moduleSpecifier: string) {
3164            // If we’re in JavaScript, it can be difficult to tell whether the user wants to import
3165            // from Node core modules or not. We can start by seeing if the user is actually using
3166            // any node core modules, as opposed to simply having @types/node accidentally as a
3167            // dependency of a dependency.
3168            if (isSourceFileJS(fromFile) && JsTyping.nodeCoreModules.has(moduleSpecifier)) {
3169                if (usesNodeCoreModules === undefined) {
3170                    usesNodeCoreModules = consumesNodeCoreModules(fromFile);
3171                }
3172                if (usesNodeCoreModules) {
3173                    return true;
3174                }
3175            }
3176            return false;
3177        }
3178
3179        function getNodeModulesPackageNameFromFileName(importedFileName: string, moduleSpecifierResolutionHost: ModuleSpecifierResolutionHost): string | undefined {
3180            if (!stringContains(importedFileName, "node_modules") && !stringContains(importedFileName, "oh_modules")) {
3181                return undefined;
3182            }
3183            const specifier = moduleSpecifiers.getNodeModulesPackageName(
3184                host.getCompilationSettings(),
3185                fromFile,
3186                importedFileName,
3187                moduleSpecifierResolutionHost,
3188                preferences,
3189            );
3190
3191            if (!specifier) {
3192                return undefined;
3193            }
3194            // Paths here are not node_modules, so we don’t care about them;
3195            // returning anything will trigger a lookup in package.json.
3196            if (!pathIsRelative(specifier) && !isRootedDiskPath(specifier)) {
3197                return getNodeModuleRootSpecifier(specifier);
3198            }
3199        }
3200
3201        function getNodeModuleRootSpecifier(fullSpecifier: string): string {
3202            const components = getPathComponents(getPackageNameFromTypesPackageName(fullSpecifier)).slice(1);
3203            // Scoped packages
3204            if (startsWith(components[0], "@")) {
3205                return `${components[0]}/${components[1]}`;
3206            }
3207            return components[0];
3208        }
3209    }
3210
3211    function tryParseJson(text: string) {
3212        try {
3213            return JSON.parse(text);
3214        }
3215        catch {
3216            return undefined;
3217        }
3218    }
3219
3220    export function consumesNodeCoreModules(sourceFile: SourceFile): boolean {
3221        return some(sourceFile.imports, ({ text }) => JsTyping.nodeCoreModules.has(text));
3222    }
3223
3224    export function isInsideNodeModules(fileOrDirectory: string): boolean {
3225        return contains(getPathComponents(fileOrDirectory), "node_modules");
3226    }
3227
3228    export function isDiagnosticWithLocation(diagnostic: Diagnostic): diagnostic is DiagnosticWithLocation {
3229        return diagnostic.file !== undefined && diagnostic.start !== undefined && diagnostic.length !== undefined;
3230    }
3231
3232    export function findDiagnosticForNode(node: Node, sortedFileDiagnostics: readonly Diagnostic[]): DiagnosticWithLocation | undefined {
3233        const span: Partial<TextSpan> = createTextSpanFromNode(node);
3234        const index = binarySearchKey(sortedFileDiagnostics, span, identity, compareTextSpans);
3235        if (index >= 0) {
3236            const diagnostic = sortedFileDiagnostics[index];
3237            Debug.assertEqual(diagnostic.file, node.getSourceFile(), "Diagnostics proided to 'findDiagnosticForNode' must be from a single SourceFile");
3238            return cast(diagnostic, isDiagnosticWithLocation);
3239        }
3240    }
3241
3242    export function getDiagnosticsWithinSpan(span: TextSpan, sortedFileDiagnostics: readonly Diagnostic[]): readonly DiagnosticWithLocation[] {
3243        let index = binarySearchKey(sortedFileDiagnostics, span.start, diag => diag.start, compareValues);
3244        if (index < 0) {
3245            index = ~index;
3246        }
3247        while (sortedFileDiagnostics[index - 1]?.start === span.start) {
3248            index--;
3249        }
3250
3251        const result: DiagnosticWithLocation[] = [];
3252        const end = textSpanEnd(span);
3253        while (true) {
3254            const diagnostic = tryCast(sortedFileDiagnostics[index], isDiagnosticWithLocation);
3255            if (!diagnostic || diagnostic.start > end) {
3256                break;
3257            }
3258            if (textSpanContainsTextSpan(span, diagnostic)) {
3259                result.push(diagnostic);
3260            }
3261            index++;
3262        }
3263
3264        return result;
3265    }
3266
3267    /* @internal */
3268    export function getRefactorContextSpan({ startPosition, endPosition }: RefactorContext): TextSpan {
3269        return createTextSpanFromBounds(startPosition, endPosition === undefined ? startPosition : endPosition);
3270    }
3271
3272    /* @internal */
3273    export function getFixableErrorSpanExpression(sourceFile: SourceFile, span: TextSpan): Expression | undefined {
3274        const token = getTokenAtPosition(sourceFile, span.start);
3275        // Checker has already done work to determine that await might be possible, and has attached
3276        // related info to the node, so start by finding the expression that exactly matches up
3277        // with the diagnostic range.
3278        const expression = findAncestor(token, node => {
3279            if (node.getStart(sourceFile) < span.start || node.getEnd() > textSpanEnd(span)) {
3280                return "quit";
3281            }
3282            return isExpression(node) && textSpansEqual(span, createTextSpanFromNode(node, sourceFile));
3283        }) as Expression | undefined;
3284
3285        return expression;
3286    }
3287
3288    /**
3289     * If the provided value is an array, the mapping function is applied to each element; otherwise, the mapping function is applied
3290     * to the provided value itself.
3291     */
3292    export function mapOneOrMany<T, U>(valueOrArray: T | readonly T[], f: (x: T, i: number) => U): U | U[];
3293    export function mapOneOrMany<T, U>(valueOrArray: T | readonly T[] | undefined, f: (x: T, i: number) => U): U | U[] | undefined;
3294    export function mapOneOrMany<T, U>(valueOrArray: T | readonly T[], f: (x: T, i: number) => U, resultSelector: (x: U[]) => U): U;
3295    export function mapOneOrMany<T, U>(valueOrArray: T | readonly T[] | undefined, f: (x: T, i: number) => U, resultSelector: (x: U[]) => U): U | undefined;
3296    export function mapOneOrMany<T, U>(valueOrArray: T | readonly T[] | undefined, f: (x: T, i: number) => U, resultSelector: (x: U[]) => U | U[] = identity): U | U[] | undefined {
3297        return valueOrArray ? isArray(valueOrArray) ? resultSelector(map(valueOrArray, f)) : f(valueOrArray, 0) : undefined;
3298    }
3299
3300    /**
3301     * If the provided value is an array, the first element of the array is returned; otherwise, the provided value is returned instead.
3302     */
3303    export function firstOrOnly<T>(valueOrArray: T | readonly T[]): T {
3304        return isArray(valueOrArray) ? first(valueOrArray) : valueOrArray;
3305    }
3306
3307    export function getNamesForExportedSymbol(symbol: Symbol, scriptTarget: ScriptTarget | undefined): string | [lowercase: string, capitalized: string] {
3308        if (needsNameFromDeclaration(symbol)) {
3309            const fromDeclaration = getDefaultLikeExportNameFromDeclaration(symbol);
3310            if (fromDeclaration) return fromDeclaration;
3311            const fileNameCase = codefix.moduleSymbolToValidIdentifier(getSymbolParentOrFail(symbol), scriptTarget, /*preferCapitalized*/ false);
3312            const capitalized = codefix.moduleSymbolToValidIdentifier(getSymbolParentOrFail(symbol), scriptTarget, /*preferCapitalized*/ true);
3313            if (fileNameCase === capitalized) return fileNameCase;
3314            return [fileNameCase, capitalized];
3315        }
3316        return symbol.name;
3317    }
3318
3319    export function getNameForExportedSymbol(symbol: Symbol, scriptTarget: ScriptTarget | undefined, preferCapitalized?: boolean) {
3320        if (needsNameFromDeclaration(symbol)) {
3321            // Name of "export default foo;" is "foo". Name of "export default 0" is the filename converted to camelCase.
3322            return getDefaultLikeExportNameFromDeclaration(symbol)
3323                || codefix.moduleSymbolToValidIdentifier(getSymbolParentOrFail(symbol), scriptTarget, !!preferCapitalized);
3324        }
3325        return symbol.name;
3326
3327    }
3328
3329    function needsNameFromDeclaration(symbol: Symbol) {
3330        return !(symbol.flags & SymbolFlags.Transient) && (symbol.escapedName === InternalSymbolName.ExportEquals || symbol.escapedName === InternalSymbolName.Default);
3331    }
3332
3333    function getDefaultLikeExportNameFromDeclaration(symbol: Symbol) {
3334        return firstDefined(symbol.declarations, d => isExportAssignment(d) ? tryCast(skipOuterExpressions(d.expression), isIdentifier)?.text : undefined);
3335    }
3336
3337    function getSymbolParentOrFail(symbol: Symbol) {
3338        return Debug.checkDefined(
3339            symbol.parent,
3340            `Symbol parent was undefined. Flags: ${Debug.formatSymbolFlags(symbol.flags)}. ` +
3341            `Declarations: ${symbol.declarations?.map(d => {
3342                const kind = Debug.formatSyntaxKind(d.kind);
3343                const inJS = isInJSFile(d);
3344                const { expression } = d as any;
3345                return (inJS ? "[JS]" : "") + kind + (expression ? ` (expression: ${Debug.formatSyntaxKind(expression.kind)})` : "");
3346            }).join(", ")}.`);
3347    }
3348
3349    /**
3350     * Useful to check whether a string contains another string at a specific index
3351     * without allocating another string or traversing the entire contents of the outer string.
3352     *
3353     * This function is useful in place of either of the following:
3354     *
3355     * ```ts
3356     * // Allocates
3357     * haystack.substr(startIndex, needle.length) === needle
3358     *
3359     * // Full traversal
3360     * haystack.indexOf(needle, startIndex) === startIndex
3361     * ```
3362     *
3363     * @param haystack The string that potentially contains `needle`.
3364     * @param needle The string whose content might sit within `haystack`.
3365     * @param startIndex The index within `haystack` to start searching for `needle`.
3366     */
3367    export function stringContainsAt(haystack: string, needle: string, startIndex: number) {
3368        const needleLength = needle.length;
3369        if (needleLength + startIndex > haystack.length) {
3370            return false;
3371        }
3372        for (let i = 0; i < needleLength; i++) {
3373            if (needle.charCodeAt(i) !== haystack.charCodeAt(i + startIndex)) return false;
3374        }
3375        return true;
3376    }
3377
3378    export function startsWithUnderscore(name: string): boolean {
3379        return name.charCodeAt(0) === CharacterCodes._;
3380    }
3381
3382    export function isGlobalDeclaration(declaration: Declaration) {
3383        return !isNonGlobalDeclaration(declaration);
3384    }
3385
3386    export function isNonGlobalDeclaration(declaration: Declaration) {
3387        const sourceFile = declaration.getSourceFile();
3388        // If the file is not a module, the declaration is global
3389        if (!sourceFile.externalModuleIndicator && !sourceFile.commonJsModuleIndicator) {
3390            return false;
3391        }
3392        // If the file is a module written in TypeScript, it still might be in a `declare global` augmentation
3393        return isInJSFile(declaration) || !findAncestor(declaration, isGlobalScopeAugmentation);
3394    }
3395
3396    export function isDeprecatedDeclaration(decl: Declaration) {
3397        return !!(getCombinedNodeFlagsAlwaysIncludeJSDoc(decl) & ModifierFlags.Deprecated);
3398    }
3399
3400    export function shouldUseUriStyleNodeCoreModules(file: SourceFile, program: Program): boolean {
3401        const decisionFromFile = firstDefined(file.imports, node => {
3402            if (JsTyping.nodeCoreModules.has(node.text)) {
3403                return startsWith(node.text, "node:");
3404            }
3405        });
3406        return decisionFromFile ?? program.usesUriStyleNodeCoreModules;
3407    }
3408
3409    export function getNewLineKind(newLineCharacter: string): NewLineKind {
3410        return newLineCharacter === "\n" ? NewLineKind.LineFeed : NewLineKind.CarriageReturnLineFeed;
3411    }
3412
3413    export type DiagnosticAndArguments = DiagnosticMessage | [DiagnosticMessage, string] | [DiagnosticMessage, string, string];
3414    export function diagnosticToString(diag: DiagnosticAndArguments): string {
3415        return isArray(diag)
3416            ? formatStringFromArgs(getLocaleSpecificMessage(diag[0]), diag.slice(1) as readonly string[])
3417            : getLocaleSpecificMessage(diag);
3418    }
3419
3420    /**
3421     * Get format code settings for a code writing context (e.g. when formatting text changes or completions code).
3422     */
3423    export function getFormatCodeSettingsForWriting({ options }: formatting.FormatContext, sourceFile: SourceFile): FormatCodeSettings {
3424        const shouldAutoDetectSemicolonPreference = !options.semicolons || options.semicolons === SemicolonPreference.Ignore;
3425        const shouldRemoveSemicolons = options.semicolons === SemicolonPreference.Remove || shouldAutoDetectSemicolonPreference && !probablyUsesSemicolons(sourceFile);
3426        return {
3427            ...options,
3428            semicolons: shouldRemoveSemicolons ? SemicolonPreference.Remove : SemicolonPreference.Ignore,
3429        };
3430    }
3431
3432    export function jsxModeNeedsExplicitImport(jsx: JsxEmit | undefined) {
3433        return jsx === JsxEmit.React || jsx === JsxEmit.ReactNative;
3434    }
3435
3436    export function isSourceFileFromLibrary(program: Program, node: SourceFile) {
3437        return program.isSourceFileFromExternalLibrary(node) || program.isSourceFileDefaultLibrary(node);
3438    }
3439
3440    export function isVirtualConstructor(checker: TypeChecker, symbol: Symbol, node: Node): boolean {
3441        const symbolName = checker.symbolToString(symbol); // Do not get scoped name, just the name of the symbol
3442        const symbolKind = SymbolDisplay.getSymbolKind(checker, symbol, node);
3443        if (node.virtual && symbolName === InternalSymbolName.Constructor && symbolKind === ScriptElementKind.constructorImplementationElement) {
3444            return true;
3445        }
3446        return false;
3447    }
3448
3449    export function getDeclarationFromSymbol(symbol: Symbol | undefined, position = "first"): Declaration | undefined {
3450        return symbol?.valueDeclaration ?? (symbol?.declarations && symbol.declarations.length ? position === "first" ? first(symbol.declarations) : last(symbol.declarations) : undefined);
3451    }
3452
3453    export function isVirtualAttributeTypeArgument(node: CallExpression | EtsComponentExpression): boolean {
3454        return node.typeArguments ?
3455            some(node.typeArguments,
3456                (argument) => isTypeReferenceNode(argument) &&
3457                !!argument.virtual &&
3458                isIdentifier(argument.typeName) &&
3459                !!argument.typeName.escapedText.toString().match("Attribute")
3460            ) : true;
3461    }
3462
3463    export function getTextOfJSDocTagInfo(tag: JSDocTagInfo): string {
3464        if (!tag.text) {
3465            return "";
3466        }
3467        if (Array.isArray(tag.text)) {
3468            return displayPartsToString(tag.text);
3469        } else {
3470            return getTextOfJSDocComment(tag.text) ?? "";
3471        }
3472    }
3473
3474    // #endregion
3475}
3476