Proposed module resolution strategy

UPDATE: proposal below is updated based on the results of the design meeting.
Initial version can be found here.

Primary differences:

• instead of having baseUrl as a separate module resolution strategy we are introducing a set of properties
  that will allow to customize resoluton process in existing resolution strategies but base strategy still is used as a fallback.
• rootDirs are decoupled from the baseUrl and can be used without it.

Currently TypeScript supports two ways of resolving module names: classic (module name always resolves to a file, module are searched using a folder walk)
and node (uses rules similar to node module loader, was introduced in TypeScript 1.6).
These approaches worked reasonably well but they were not able to model baseUrl based mechanics used by
RequireJS or SystemJS.

We could introduce third type of module resolution that will fill this gap but this will mean that once user has started to use this new type then support to
discover typings embedded in node modules (and distributed via npm) is lost. Effectively user that wanted both to use baseUrl to refer to modules defined inside the project
and rely on npm to obtain modules with typings will have to choose what part of the system will be broken.

Instead of doing this we'll allow to declare a set of properties that will augment existing module resolution strategies. These properties are:
baseUrl, paths and rootDirs (paths can only be used if baseUrl is set). If at least one of these properties is defined then compiler will try to
use it to resolve module name and if it fail - will fallback to a default behavior for a current resolution strategy.

Also choice of resolution strategy determines what does it mean to load a module from a given path. To be more concrete given some module name /a/b/c:

• classic resolver will check for the presense of files /a/b/c.ts, /a/b/c.tsx and /a/b/c.d.ts.
• node resolver will first try to load module as file by probing the same files as classic and then try to load module from directory
  (check /a/b/c/index with supported extension, then peek into package.json etc. More details can be found in this issue)

Properties

• baseUrl
• path mappings
• rootDirs

BaseUrl

All non-rooted paths are computed relative to baseUrl.
Value of baseUrl is determined as either:

• value of baseUrl command line argument (if given path is relative it is computed based on current directory)
• value of baseUrl propery in 'tsconfig.json' (if given path is relative it is computed based on then location of 'tsconfig.json')

Path mappings

Sometimes modules are not directly located under baseUrl. It is possible to control how locations are computed in such cases
using path mappings. Path mappings are specified using the following JSON structure:

{
    "paths": {
        "pattern-1": ["list of substitutions"],
        "pattern-2": ["list of substitutions"],
        ...
        "pattern-N": ["list of substitutions"]
    }
}

Patterns and substitutions are strings that can have zero or one asteriks ('*').
Interpretation of both patterns and substitutions will be described in Resolution process section.

Resolution process

Non-relative module names are resolved slightly differently comparing
to relative (start with "./" or "../") and rooted module names (start with "/", drive name or schema).

Resolution of non-relative module names (mostly matches SystemJS)

// mimics path mappings in SystemJS
// NOTE: moduleExists checks if file with any supported extension exists on disk
function resolveNonRelativeModuleName(moduleName: string): string {
    // check if module name should be used as-is or it should be mapped to different value
    let longestMatchedPrefixLength = 0;
    let matchedPattern: string;
    let matchedWildcard: string;

    for (let pattern in config.paths) {
        assert(pattern.countOf('*') <= 1);
        let indexOfWildcard = pattern.indexOf('*'); 
        if (indexOfWildcard !== -1) {
            // if pattern contains asterisk then asterisk acts as a capture group with a greedy matching
            // i.e. for the string 'abbb' pattern 'a*b' will get 'bb' as '*'

            // check if module name starts with prefix, ends with suffix and these two don't overlap
            let prefix = pattern.substr(0, indexOfWildcard);
            let suffix = pattern.substr(indexOfWildcard + 1);
            if (moduleName.length >= prefix.length + suffix.length && 
                moduleName.startsWith(prefix) &&
                moduleName.endsWith(suffix)) {

                // use length of matched prefix as betterness criteria
                if (longestMatchedPrefixLength < prefix.length) {
                    // save length of the prefix
                    longestMatchedPrefixLength = prefix.length;
                    // save matched pattern
                    matchedPattern = pattern;
                    // save matched wildcard content 
                    matchedWildcard = moduleName.substr(prefix.length, moduleName.length - suffix.length);
                }
            }
        }
        else {
            // pattern does not contain asterisk - module name should exactly match pattern to succeed
            if (pattern === moduleName) {
                // save pattern
                matchedPattern = pattern;
                // drop saved wildcard match 
                matchedWildcard = undefined;
                // exact match is found - can exit early 
                break;
            }
        }
    }

    if (!matchedPattern) {
        // no pattern was matched so module name can be used as-is
        let path = combine(baseUrl, moduleName);
        return moduleExists(path) ? path : undefined;
    }

    // some pattern was matched - module name needs to be substituted
    let substitutions = config.paths[matchedPattern].asArray();
    for (let subst of substitutions) {
        assert(substs.countOf('*') <= 1);
        // replace * in substitution with matched wildcard
        let path = matchedWildcard ? subst.replace("*", matchedWildcard) : subst;
        // if substituion is a relative path - combine it with baseUrl
        path = isRelative(path) ? combine(baseUrl, path) : path;
        if (moduleExists(path)) {
            return path;
        }
    }

    return undefined;   
}

Resolution of relative module names

Default resolution logic (matches SystemJS)

Relative module names are computed treating location of source file that contains the import as base folder.
Path mappings are not applied.

function resolveRelativeModuleName(moduleName: string, containingFile: string): string {
    let path = combine(getDirectoryName(containingFile), moduleName);
    return moduleExists(path) ? path : undefined;
}

Using rootDirs

'rootDirs' allows the project to be spreaded across multiple locations and resolve modules with relative names as if multiple project roots were merged together in one folder. For example project contains source files that are located in different directories on then file system (not under the same root) but user still still prefers to use relative module names because in runtime such names can be successfully resolved due to bundling.

For example consider this project structure:

 shared
 └── projects
     └── project
         └── src
             ├── viewManager.ts (imports './views/view1')
             └── views
                 └── view2.ts (imports './view1')
 userFiles
 └── project
     └── src
         └── views
             └── view1.ts (imports './view2')

Logically files in userFiles/project and shared/projects/project belong to the same project and
after build they indeed will be bundled together.

In order to support this we'll add configuration property "rootDirs":

{
    "rootDirs": [
        "rootDir-1/",
        "rootDir-2/",
        ...
        "rootDir-n/"
    ]
}

This property stores list of base folders, every folder name can be either absolute or relative.
Elements in rootDirs that represent non-absolute paths will be converted to absolute using location of tsconfig.json as a base folder - this is the common approach for all paths defined in tsconfig.json

///Algorithm for resolving relative module name
function resolveRelativeModuleName(moduleName: string, containingFile: string): string {
    // convert relative module name to absolute using location of containing file
    // this step is exactly the same as when doing resolution without path mapping
    let path = combine(getDirectoryName(containingFile), moduleName);

    // convert absolute module name to non-relative
    // try to find element in 'rootDirs' that is the longest prefix for "path' and return path.substr(prefix.length) as non-relative name
    let { matchingRootDir, nonRelativeName } = tryFindLongestPrefixAndReturnSuffix(rootDirs, path);
    if (!matchingRootDir) {
        // cannot extract non relative name
        return undefined;
    }
    // first try to load module from initial location
    if (moduleExists(path)) {
        return path;
    }
    // then try other entries in rootDirs
    for (const rootDir of rootDirs) {
        if (rootDir === matchingRootDir) {
            continue;
        }
        const candidate = combine(rootDir, nonRelativeName);
        if (moduleExists(candidate)) {
            return candidate;
        }
    }
    // failure case
    return undefined;
}

Configuration for the example above:

{
    "rootDirs": [
        "userFiles/project/",
        "/shared/projects/project/"
    ]
}

Example 1

projectRoot
├── folder1
│   └── file1.ts (imports 'folder2/file2')
├── folder2
│   ├── file2.ts (imports './file3')
│   └── file3.ts
└── tsconfig.json

// configuration in tsconfig.json
{
    "baseUrl": "."
}

• import 'folder2/file2'
  1. baseUrl is specified in configuration and has value '.' -> baseUrl is computed relative to
     the location of tsconfig.json -> projectRoot
  2. path mappings are not available -> path = moduleName
  3. resolved module file name = combine(baseUrl, path) -> projectRoot/folder2/file2.ts
• import './file3'
  1. moduleName is relative and rootDirs are not specified in configuration - compute module name
     relative to the location of containing file: resolved module file name = projectRoot/folder2/file3.ts

Example 2

projectRoot
├── folder1
│   ├── file1.ts (imports 'folder1/file2' and 'folder2/file3')
│   └── file2.ts
├── generated
│   ├── folder1
│   └── folder2
│       └── file3.ts
└── tsconfig.json

// configuration in tsconfig.json
{
    "baseUrl": ".",
    "paths": {
    "*": [
            "*",
            "generated/*" 
        ]
    }
}

• import 'folder1/file2'
  1. baseUrl is specified in configuration and has value '.' -> baseUrl is computed relative to
     the location of tsconfig.json -> projectRoot
  2. configuration contains path mappings.
  3. pattern '*' is matched and wildcard captures the whole module name
  4. try first substitution in the list: '*' -> folder1/file2
  5. result of substitution is relative name - combine it with baseUrl -> projectRoot/folder1/file2.ts.
     This file exists.
• import 'folder2/file2'
  1. baseUrl is specified in configuration and has value '.' -> baseUrl is computed relative to
     the location of tsconfig.json and will be folder that contains tsconfig.json
  2. configuration contains path mappings.
  3. pattern '*' is matched and wildcard captures the whole module name
  4. try first substitution in the list: '*' -> folder2/file3
  5. result of substitution is relative name - combine it with baseUrl -> projectRoot/folder2/file3.ts.
     File does not exists, move to the second substitution
  6. second substitution 'generated/*' -> generated/folder2/file3
  7. result of substitution is relative name - combine it with baseUrl -> projectRoot/generated/folder2/file3.ts.
     File exists

Example 3

rootDir
├── folder1
│   └── file1.ts (imports './file2')
├── generated
│   ├── folder1
│   │   ├── file2.ts
│   │   └── file3.ts (imports '../folder1/file1')
│   └── folder2
└── tsconfig.json

// configuration in tsconfig.json
{
    "rootDirs": [
        "./",
        "./generated/" 
    ],
}

All non-rooted entries in rootDirs are expanded using location of tsconfig.json as base location so after expansion rootDirs will
look like this:

    "rootDirs": [
        "rootDir/",
        "rootDir/generated/" 
    ],

• import './file2'
  1. name is relative, first make it absolute using location of containing file as base location - rootDir/folder1/file2
  2. for this string find the longest prefix in rootDirs - rootDir/ and for this prefix compute as suffix - folder1/file2
  3. since matching entry in rootDirs was found try to resolve module using rootDir - first check if rootDir/folder1/file2
     can be resolved as module - such module does not exist
  4. try remaining entries in rootDirs - check if module rootDir/generated/folder1/file2 exists - yes.
• import '../folder1/file1'
  1. name is relative, first make it absolute using location of containing file as base location - rootDir/generated/folder1/file1
  2. for this string find the longest prefix in rootDirs - rootDir/generated and for this prefix compute as suffix - folder1/file1
  3. since matching entry in rootDirs was found try to resolve module using rootDir - first check if rootDir/generated/folder1/file1
     can be resolved as module - such module does not exist
  4. try remaining entries in rootDirs - check if module rootDir/folder1/file1 exists - yes.