Spelling Correction in TypeScript

TypeScript 2.4 implemented a spelling correction mechanism for identifiers. Even if you slightly misspell a variable, property, or function name, the TypeScript language service can suggest the correct spelling in many cases.

#Spelling Corrections in Action

Let's say you want to call window.location.reload() to reload the current page in a web application. If you accidentally type locatoin or make some other typo, the TypeScript language service will suggest the correct spelling and offer a quick fix:

This correction mechanism is especially helpful for names that are commonly misspelled. Take the word "referrer", for example. Instead of document.referrer, you might write any of the following:

• document.referer
• document.refferer
• document.refferrer

TypeScript will recognize all of these misspellings and suggest document.referrer as the correct spelling. It'll even recognize and correct all of the following (more exotic) variants:

• document.referrerer
• document.referrawr
• document.refferrrr

Of course, you won't need spelling suggestions if you just type document.ref and then hit TAB or ENTER to have TypeScript complete the name for you, but if you quickly type the entire property name yourself, chances are you'll make a typo.

#Levenshtein Distance and Heuristics

Internally, TypeScript computes the Levenshtein distance between the misspelled name and each candidate in a list of names which are available at that location in the program. The best match (if any) is then returned as a spelling suggestion.

The algorithm is implemented in the getSpellingSuggestionForName function within the checker.ts file of the TypeScript compiler. At the time of writing, it looks as follows:

/**
 * Given a name and a list of symbols whose names are *not* equal to the name, return a spelling suggestion if there is one that is close enough.
 * Names less than length 3 only check for case-insensitive equality, not levenshtein distance.
 *
 * If there is a candidate that's the same except for case, return that.
 * If there is a candidate that's within one edit of the name, return that.
 * Otherwise, return the candidate with the smallest Levenshtein distance,
 *    except for candidates:
 *      * With no name
 *      * Whose meaning doesn't match the `meaning` parameter.
 *      * Whose length differs from the target name by more than 0.34 of the length of the name.
 *      * Whose levenshtein distance is more than 0.4 of the length of the name
 *        (0.4 allows 1 substitution/transposition for every 5 characters,
 *         and 1 insertion/deletion at 3 characters)
 */
function getSpellingSuggestionForName(name: string, symbols: Symbol[], meaning: SymbolFlags): Symbol | undefined {
    const maximumLengthDifference = Math.min(2, Math.floor(name.length * 0.34));
    let bestDistance = Math.floor(name.length * 0.4) + 1; // If the best result isn't better than this, don't bother.
    let bestCandidate: Symbol | undefined;
    let justCheckExactMatches = false;
    const nameLowerCase = name.toLowerCase();
    for (const candidate of symbols) {
        const candidateName = symbolName(candidate);
        if (!(candidate.flags & meaning && Math.abs(candidateName.length - nameLowerCase.length) <= maximumLengthDifference)) {
            continue;
        }
        const candidateNameLowerCase = candidateName.toLowerCase();
        if (candidateNameLowerCase === nameLowerCase) {
            return candidate;
        }
        if (justCheckExactMatches) {
            continue;
        }
        if (candidateName.length < 3) {
            // Don't bother, user would have noticed a 2-character name having an extra character
            continue;
        }
        // Only care about a result better than the best so far.
        const distance = levenshteinWithMax(nameLowerCase, candidateNameLowerCase, bestDistance - 1);
        if (distance === undefined) {
            continue;
        }
        if (distance < 3) {
            justCheckExactMatches = true;
            bestCandidate = candidate;
        }
        else {
            Debug.assert(distance < bestDistance); // Else `levenshteinWithMax` should return undefined
            bestDistance = distance;
            bestCandidate = candidate;
        }
    }
    return bestCandidate;
}

The getSpellingSuggestionForName uses a bunch of heuristics to produce a reasonable spelling suggestion that's neither too strict nor too permissive — an interesting balance to strike, if you ask me!