/*!
 * @license
 * Copyright Google LLC All Rights Reserved.
 *
 * Use of this source code is governed by an MIT-style license that can be
 * found in the LICENSE file at https://angular.io/license
 */


import {NgtscProgram} from '@angular/compiler-cli';
import {TemplateTypeChecker} from '@angular/compiler-cli/private/migrations';
import {dirname, join} from 'path';
import ts from 'typescript';

import {ChangeTracker, ImportRemapper} from '../../utils/change_tracker';
import {getAngularDecorators} from '../../utils/ng_decorators';
import {closestNode} from '../../utils/typescript/nodes';

import {ComponentImportsRemapper, convertNgModuleDeclarationToStandalone, extractDeclarationsFromModule, findTestObjectsToMigrate, migrateTestDeclarations} from './to-standalone';
import {closestOrSelf, findClassDeclaration, findLiteralProperty, getNodeLookup, getRelativeImportPath, isClassReferenceInAngularModule, NamedClassDeclaration, NodeLookup, offsetsToNodes, ReferenceResolver, UniqueItemTracker} from './util';

/** Information extracted from a `bootstrapModule` call necessary to migrate it. */
interface BootstrapCallAnalysis {
  /** The call itself. */
  call: ts.CallExpression;
  /** Class that is being bootstrapped. */
  module: ts.ClassDeclaration;
  /** Metadata of the module class being bootstrapped. */
  metadata: ts.ObjectLiteralExpression;
  /** Component that the module is bootstrapping. */
  component: NamedClassDeclaration;
  /** Classes declared by the bootstrapped module. */
  declarations: ts.ClassDeclaration[];
}

export function toStandaloneBootstrap(
    program: NgtscProgram, host: ts.CompilerHost, basePath: string, rootFileNames: string[],
    sourceFiles: ts.SourceFile[], printer: ts.Printer, importRemapper?: ImportRemapper,
    referenceLookupExcludedFiles?: RegExp, componentImportRemapper?: ComponentImportsRemapper) {
  const tracker = new ChangeTracker(printer, importRemapper);
  const typeChecker = program.getTsProgram().getTypeChecker();
  const templateTypeChecker = program.compiler.getTemplateTypeChecker();
  const referenceResolver =
      new ReferenceResolver(program, host, rootFileNames, basePath, referenceLookupExcludedFiles);
  const bootstrapCalls: BootstrapCallAnalysis[] = [];
  const testObjects = new Set<ts.ObjectLiteralExpression>();
  const allDeclarations = new Set<ts.ClassDeclaration>();

  // `bootstrapApplication` doesn't include Protractor support by default
  // anymore so we have to opt the app in, if we detect it being used.
  const additionalProviders = hasImport(program, rootFileNames, 'protractor') ?
      new Map([['provideProtractorTestingSupport', '@angular/platform-browser']]) :
      null;

  for (const sourceFile of sourceFiles) {
    sourceFile.forEachChild(function walk(node) {
      if (ts.isCallExpression(node) && ts.isPropertyAccessExpression(node.expression) &&
          node.expression.name.text === 'bootstrapModule' &&
          isClassReferenceInAngularModule(node.expression, 'PlatformRef', 'core', typeChecker)) {
        const call = analyzeBootstrapCall(node, typeChecker, templateTypeChecker);

        if (call) {
          bootstrapCalls.push(call);
        }
      }
      node.forEachChild(walk);
    });

    findTestObjectsToMigrate(sourceFile, typeChecker).forEach(obj => testObjects.add(obj));
  }

  for (const call of bootstrapCalls) {
    call.declarations.forEach(decl => allDeclarations.add(decl));
    migrateBootstrapCall(
        call, tracker, additionalProviders, referenceResolver, typeChecker, printer);
  }

  // The previous migrations explicitly skip over bootstrapped
  // declarations so we have to migrate them now.
  for (const declaration of allDeclarations) {
    convertNgModuleDeclarationToStandalone(
        declaration, allDeclarations, tracker, templateTypeChecker, componentImportRemapper);
  }

  migrateTestDeclarations(testObjects, allDeclarations, tracker, templateTypeChecker, typeChecker);
  return tracker.recordChanges();
}

/**
 * Extracts all of the information from a `bootstrapModule` call
 * necessary to convert it to `bootstrapApplication`.
 * @param call Call to be analyzed.
 * @param typeChecker
 * @param templateTypeChecker
 */
function analyzeBootstrapCall(
    call: ts.CallExpression, typeChecker: ts.TypeChecker,
    templateTypeChecker: TemplateTypeChecker): BootstrapCallAnalysis|null {
  if (call.arguments.length === 0 || !ts.isIdentifier(call.arguments[0])) {
    return null;
  }

  const declaration = findClassDeclaration(call.arguments[0], typeChecker);

  if (!declaration) {
    return null;
  }

  const decorator = getAngularDecorators(typeChecker, ts.getDecorators(declaration) || [])
                        .find(decorator => decorator.name === 'NgModule');

  if (!decorator || decorator.node.expression.arguments.length === 0 ||
      !ts.isObjectLiteralExpression(decorator.node.expression.arguments[0])) {
    return null;
  }

  const metadata = decorator.node.expression.arguments[0];
  const bootstrapProp = findLiteralProperty(metadata, 'bootstrap');

  if (!bootstrapProp || !ts.isPropertyAssignment(bootstrapProp) ||
      !ts.isArrayLiteralExpression(bootstrapProp.initializer) ||
      bootstrapProp.initializer.elements.length === 0 ||
      !ts.isIdentifier(bootstrapProp.initializer.elements[0])) {
    return null;
  }

  const component = findClassDeclaration(bootstrapProp.initializer.elements[0], typeChecker);

  if (component && component.name && ts.isIdentifier(component.name)) {
    return {
      module: declaration,
      metadata,
      component: component as NamedClassDeclaration,
      call,
      declarations: extractDeclarationsFromModule(declaration, templateTypeChecker)
    };
  }

  return null;
}

/**
 * Converts a `bootstrapModule` call to `bootstrapApplication`.
 * @param analysis Analysis result of the call.
 * @param tracker Tracker in which to register the changes.
 * @param additionalFeatures Additional providers, apart from the auto-detected ones, that should
 * be added to the bootstrap call.
 * @param referenceResolver
 * @param typeChecker
 * @param printer
 */
function migrateBootstrapCall(
    analysis: BootstrapCallAnalysis, tracker: ChangeTracker,
    additionalProviders: Map<string, string>|null, referenceResolver: ReferenceResolver,
    typeChecker: ts.TypeChecker, printer: ts.Printer) {
  const sourceFile = analysis.call.getSourceFile();
  const moduleSourceFile = analysis.metadata.getSourceFile();
  const providers = findLiteralProperty(analysis.metadata, 'providers');
  const imports = findLiteralProperty(analysis.metadata, 'imports');
  const nodesToCopy = new Set<ts.Node>();
  const providersInNewCall: ts.Expression[] = [];
  const moduleImportsInNewCall: ts.Expression[] = [];
  let nodeLookup: NodeLookup|null = null;

  // Comment out the metadata so that it'll be removed when we run the module pruning afterwards.
  // If the pruning is left for some reason, the user will still have an actionable TODO.
  tracker.insertText(
      moduleSourceFile, analysis.metadata.getStart(),
      '/* TODO(standalone-migration): clean up removed NgModule class manually. \n');
  tracker.insertText(moduleSourceFile, analysis.metadata.getEnd(), ' */');

  if (providers && ts.isPropertyAssignment(providers)) {
    nodeLookup = nodeLookup || getNodeLookup(moduleSourceFile);

    if (ts.isArrayLiteralExpression(providers.initializer)) {
      providersInNewCall.push(...providers.initializer.elements);
    } else {
      providersInNewCall.push(ts.factory.createSpreadElement(providers.initializer));
    }

    addNodesToCopy(sourceFile, providers, nodeLookup, tracker, nodesToCopy, referenceResolver);
  }

  if (imports && ts.isPropertyAssignment(imports)) {
    nodeLookup = nodeLookup || getNodeLookup(moduleSourceFile);
    migrateImportsForBootstrapCall(
        sourceFile, imports, nodeLookup, moduleImportsInNewCall, providersInNewCall, tracker,
        nodesToCopy, referenceResolver, typeChecker);
  }

  if (additionalProviders) {
    additionalProviders.forEach((moduleSpecifier, name) => {
      providersInNewCall.push(ts.factory.createCallExpression(
          tracker.addImport(sourceFile, name, moduleSpecifier), undefined, undefined));
    });
  }

  if (nodesToCopy.size > 0) {
    let text = '\n\n';
    nodesToCopy.forEach(node => {
      const transformedNode = remapDynamicImports(sourceFile.fileName, node);

      // Use `getText` to try an preserve the original formatting. This only works if the node
      // hasn't been transformed. If it has, we have to fall back to the printer.
      if (transformedNode === node) {
        text += transformedNode.getText() + '\n';
      } else {
        text += printer.printNode(ts.EmitHint.Unspecified, transformedNode, node.getSourceFile());
      }
    });
    text += '\n';
    tracker.insertText(sourceFile, getLastImportEnd(sourceFile), text);
  }

  replaceBootstrapCallExpression(analysis, providersInNewCall, moduleImportsInNewCall, tracker);
}

/**
 * Replaces a `bootstrapModule` call with `bootstrapApplication`.
 * @param analysis Analysis result of the `bootstrapModule` call.
 * @param providers Providers that should be added to the new call.
 * @param modules Modules that are being imported into the new call.
 * @param tracker Object keeping track of the changes to the different files.
 */
function replaceBootstrapCallExpression(
    analysis: BootstrapCallAnalysis, providers: ts.Expression[], modules: ts.Expression[],
    tracker: ChangeTracker): void {
  const sourceFile = analysis.call.getSourceFile();
  const componentPath =
      getRelativeImportPath(sourceFile.fileName, analysis.component.getSourceFile().fileName);
  const args = [tracker.addImport(sourceFile, analysis.component.name.text, componentPath)];
  const bootstrapExpression =
      tracker.addImport(sourceFile, 'bootstrapApplication', '@angular/platform-browser');

  if (providers.length > 0 || modules.length > 0) {
    const combinedProviders: ts.Expression[] = [];

    if (modules.length > 0) {
      const importProvidersExpression =
          tracker.addImport(sourceFile, 'importProvidersFrom', '@angular/core');
      combinedProviders.push(
          ts.factory.createCallExpression(importProvidersExpression, [], modules));
    }

    // Push the providers after `importProvidersFrom` call for better readability.
    combinedProviders.push(...providers);

    const providersArray = ts.factory.createNodeArray(
        combinedProviders,
        analysis.metadata.properties.hasTrailingComma && combinedProviders.length > 2);
    const initializer = remapDynamicImports(
        sourceFile.fileName,
        ts.factory.createArrayLiteralExpression(providersArray, combinedProviders.length > 1));

    args.push(ts.factory.createObjectLiteralExpression(
        [ts.factory.createPropertyAssignment('providers', initializer)], true));
  }

  tracker.replaceNode(
      analysis.call, ts.factory.createCallExpression(bootstrapExpression, [], args),
      // Note: it's important to pass in the source file that the nodes originated from!
      // Otherwise TS won't print out literals inside of the providers that we're copying
      // over from the module file.
      undefined, analysis.metadata.getSourceFile());
}

/**
 * Processes the `imports` of an NgModule so that they can be used in the `bootstrapApplication`
 * call inside of a different file.
 * @param sourceFile File to which the imports will be moved.
 * @param imports Node declaring the imports.
 * @param nodeLookup Map used to look up nodes based on their positions in a file.
 * @param importsForNewCall Array keeping track of the imports that are being added to the new call.
 * @param providersInNewCall Array keeping track of the providers in the new call.
 * @param tracker Tracker in which changes to files are being stored.
 * @param nodesToCopy Nodes that should be copied to the new file.
 * @param referenceResolver
 * @param typeChecker
 */
function migrateImportsForBootstrapCall(
    sourceFile: ts.SourceFile, imports: ts.PropertyAssignment, nodeLookup: NodeLookup,
    importsForNewCall: ts.Expression[], providersInNewCall: ts.Expression[], tracker: ChangeTracker,
    nodesToCopy: Set<ts.Node>, referenceResolver: ReferenceResolver,
    typeChecker: ts.TypeChecker): void {
  if (!ts.isArrayLiteralExpression(imports.initializer)) {
    importsForNewCall.push(imports.initializer);
    return;
  }

  for (const element of imports.initializer.elements) {
    // If the reference is to a `RouterModule.forRoot` call, we can try to migrate it.
    if (ts.isCallExpression(element) && ts.isPropertyAccessExpression(element.expression) &&
        element.arguments.length > 0 && element.expression.name.text === 'forRoot' &&
        isClassReferenceInAngularModule(
            element.expression.expression, 'RouterModule', 'router', typeChecker)) {
      const options = element.arguments[1] as ts.Expression | undefined;
      const features = options ? getRouterModuleForRootFeatures(sourceFile, options, tracker) : [];

      // If the features come back as null, it means that the router
      // has a configuration that can't be migrated automatically.
      if (features !== null) {
        providersInNewCall.push(ts.factory.createCallExpression(
            tracker.addImport(sourceFile, 'provideRouter', '@angular/router'), [],
            [element.arguments[0], ...features]));
        addNodesToCopy(
            sourceFile, element.arguments[0], nodeLookup, tracker, nodesToCopy, referenceResolver);
        if (options) {
          addNodesToCopy(sourceFile, options, nodeLookup, tracker, nodesToCopy, referenceResolver);
        }
        continue;
      }
    }

    if (ts.isIdentifier(element)) {
      // `BrowserAnimationsModule` can be replaced with `provideAnimations`.
      const animationsModule = 'platform-browser/animations';
      const animationsImport = `@angular/${animationsModule}`;

      if (isClassReferenceInAngularModule(
              element, 'BrowserAnimationsModule', animationsModule, typeChecker)) {
        providersInNewCall.push(ts.factory.createCallExpression(
            tracker.addImport(sourceFile, 'provideAnimations', animationsImport), [], []));
        continue;
      }

      // `NoopAnimationsModule` can be replaced with `provideNoopAnimations`.
      if (isClassReferenceInAngularModule(
              element, 'NoopAnimationsModule', animationsModule, typeChecker)) {
        providersInNewCall.push(ts.factory.createCallExpression(
            tracker.addImport(sourceFile, 'provideNoopAnimations', animationsImport), [], []));
        continue;
      }

      // `HttpClientModule` can be replaced with `provideHttpClient()`.
      const httpClientModule = 'common/http';
      const httpClientImport = `@angular/${httpClientModule}`;
      if (isClassReferenceInAngularModule(
              element, 'HttpClientModule', httpClientModule, typeChecker)) {
        const callArgs = [
          // we add `withInterceptorsFromDi()` to the call to ensure that class-based interceptors
          // still work
          ts.factory.createCallExpression(
              tracker.addImport(sourceFile, 'withInterceptorsFromDi', httpClientImport), [], [])
        ];
        providersInNewCall.push(ts.factory.createCallExpression(
            tracker.addImport(sourceFile, 'provideHttpClient', httpClientImport), [], callArgs));
        continue;
      }
    }

    const target =
        // If it's a call, it'll likely be a `ModuleWithProviders`
        // expression so the target is going to be call's expression.
        ts.isCallExpression(element) && ts.isPropertyAccessExpression(element.expression) ?
        element.expression.expression :
        element;
    const classDeclaration = findClassDeclaration(target, typeChecker);
    const decorators = classDeclaration ?
        getAngularDecorators(typeChecker, ts.getDecorators(classDeclaration) || []) :
        undefined;

    if (!decorators || decorators.length === 0 ||
        decorators.every(
            ({name}) => name !== 'Directive' && name !== 'Component' && name !== 'Pipe')) {
      importsForNewCall.push(element);
      addNodesToCopy(sourceFile, element, nodeLookup, tracker, nodesToCopy, referenceResolver);
    }
  }
}

/**
 * Generates the call expressions that can be used to replace the options
 * object that is passed into a `RouterModule.forRoot` call.
 * @param sourceFile File that the `forRoot` call is coming from.
 * @param options Node that is passed as the second argument to the `forRoot` call.
 * @param tracker Tracker in which to track imports that need to be inserted.
 * @returns Null if the options can't be migrated, otherwise an array of call expressions.
 */
function getRouterModuleForRootFeatures(
    sourceFile: ts.SourceFile, options: ts.Expression, tracker: ChangeTracker): ts.CallExpression[]|
    null {
  // Options that aren't a static object literal can't be migrated.
  if (!ts.isObjectLiteralExpression(options)) {
    return null;
  }

  const featureExpressions: ts.CallExpression[] = [];
  const configOptions: ts.PropertyAssignment[] = [];
  const inMemoryScrollingOptions: ts.PropertyAssignment[] = [];
  const features = new UniqueItemTracker<string, ts.Expression|null>();

  for (const prop of options.properties) {
    // We can't migrate options that we can't easily analyze.
    if (!ts.isPropertyAssignment(prop) ||
        (!ts.isIdentifier(prop.name) && !ts.isStringLiteralLike(prop.name))) {
      return null;
    }

    switch (prop.name.text) {
      // `preloadingStrategy` maps to the `withPreloading` function.
      case 'preloadingStrategy':
        features.track('withPreloading', prop.initializer);
        break;

      // `enableTracing: true` maps to the `withDebugTracing` feature.
      case 'enableTracing':
        if (prop.initializer.kind === ts.SyntaxKind.TrueKeyword) {
          features.track('withDebugTracing', null);
        }
        break;

      // `initialNavigation: 'enabled'` and `initialNavigation: 'enabledBlocking'` map to the
      // `withEnabledBlockingInitialNavigation` feature, while `initialNavigation: 'disabled'` maps
      // to the `withDisabledInitialNavigation` feature.
      case 'initialNavigation':
        if (!ts.isStringLiteralLike(prop.initializer)) {
          return null;
        }
        if (prop.initializer.text === 'enabledBlocking' || prop.initializer.text === 'enabled') {
          features.track('withEnabledBlockingInitialNavigation', null);
        } else if (prop.initializer.text === 'disabled') {
          features.track('withDisabledInitialNavigation', null);
        }
        break;

      // `useHash: true` maps to the `withHashLocation` feature.
      case 'useHash':
        if (prop.initializer.kind === ts.SyntaxKind.TrueKeyword) {
          features.track('withHashLocation', null);
        }
        break;

      // `errorHandler` maps to the `withNavigationErrorHandler` feature.
      case 'errorHandler':
        features.track('withNavigationErrorHandler', prop.initializer);
        break;

      // `anchorScrolling` and `scrollPositionRestoration` arguments have to be combined into an
      // object literal that is passed into the `withInMemoryScrolling` feature.
      case 'anchorScrolling':
      case 'scrollPositionRestoration':
        inMemoryScrollingOptions.push(prop);
        break;

      // All remaining properties can be passed through the `withRouterConfig` feature.
      default:
        configOptions.push(prop);
        break;
    }
  }

  if (inMemoryScrollingOptions.length > 0) {
    features.track(
        'withInMemoryScrolling',
        ts.factory.createObjectLiteralExpression(inMemoryScrollingOptions));
  }

  if (configOptions.length > 0) {
    features.track('withRouterConfig', ts.factory.createObjectLiteralExpression(configOptions));
  }

  for (const [feature, featureArgs] of features.getEntries()) {
    const callArgs: ts.Expression[] = [];
    featureArgs.forEach(arg => {
      if (arg !== null) {
        callArgs.push(arg);
      }
    });
    featureExpressions.push(ts.factory.createCallExpression(
        tracker.addImport(sourceFile, feature, '@angular/router'), [], callArgs));
  }

  return featureExpressions;
}

/**
 * Finds all the nodes that are referenced inside a root node and would need to be copied into a
 * new file in order for the node to compile, and tracks them.
 * @param targetFile File to which the nodes will be copied.
 * @param rootNode Node within which to look for references.
 * @param nodeLookup Map used to look up nodes based on their positions in a file.
 * @param tracker Tracker in which changes to files are stored.
 * @param nodesToCopy Set that keeps track of the nodes being copied.
 * @param referenceResolver
 */
function addNodesToCopy(
    targetFile: ts.SourceFile, rootNode: ts.Node, nodeLookup: NodeLookup, tracker: ChangeTracker,
    nodesToCopy: Set<ts.Node>, referenceResolver: ReferenceResolver): void {
  const refs = findAllSameFileReferences(rootNode, nodeLookup, referenceResolver);

  for (const ref of refs) {
    const importSpecifier = closestOrSelf(ref, ts.isImportSpecifier);
    const importDeclaration =
        importSpecifier ? closestNode(importSpecifier, ts.isImportDeclaration) : null;

    // If the reference is in an import, we need to add an import to the main file.
    if (importDeclaration && importSpecifier &&
        ts.isStringLiteralLike(importDeclaration.moduleSpecifier)) {
      const moduleName = importDeclaration.moduleSpecifier.text.startsWith('.') ?
          remapRelativeImport(targetFile.fileName, importDeclaration.moduleSpecifier) :
          importDeclaration.moduleSpecifier.text;
      const symbolName = importSpecifier.propertyName ? importSpecifier.propertyName.text :
                                                        importSpecifier.name.text;
      const alias = importSpecifier.propertyName ? importSpecifier.name.text : null;
      tracker.addImport(targetFile, symbolName, moduleName, alias);
      continue;
    }

    const variableDeclaration = closestOrSelf(ref, ts.isVariableDeclaration);
    const variableStatement =
        variableDeclaration ? closestNode(variableDeclaration, ts.isVariableStatement) : null;

    // If the reference is a variable, we can attempt to import it or copy it over.
    if (variableDeclaration && variableStatement && ts.isIdentifier(variableDeclaration.name)) {
      if (isExported(variableStatement)) {
        tracker.addImport(
            targetFile, variableDeclaration.name.text,
            getRelativeImportPath(targetFile.fileName, ref.getSourceFile().fileName));
      } else {
        nodesToCopy.add(variableStatement);
      }
      continue;
    }

    // Otherwise check if the reference is inside of an exportable declaration, e.g. a function.
    // This code that is safe to copy over into the new file or import it, if it's exported.
    const closestExportable = closestOrSelf(ref, isExportableDeclaration);
    if (closestExportable) {
      if (isExported(closestExportable) && closestExportable.name) {
        tracker.addImport(
            targetFile, closestExportable.name.text,
            getRelativeImportPath(targetFile.fileName, ref.getSourceFile().fileName));
      } else {
        nodesToCopy.add(closestExportable);
      }
    }
  }
}

/**
 * Finds all the nodes referenced within the root node in the same file.
 * @param rootNode Node from which to start looking for references.
 * @param nodeLookup Map used to look up nodes based on their positions in a file.
 * @param referenceResolver
 */
function findAllSameFileReferences(
    rootNode: ts.Node, nodeLookup: NodeLookup, referenceResolver: ReferenceResolver): Set<ts.Node> {
  const results = new Set<ts.Node>();
  const traversedTopLevelNodes = new Set<ts.Node>();
  const excludeStart = rootNode.getStart();
  const excludeEnd = rootNode.getEnd();

  (function walk(node) {
    if (!isReferenceIdentifier(node)) {
      node.forEachChild(walk);
      return;
    }

    const refs = referencesToNodeWithinSameFile(
        node, nodeLookup, excludeStart, excludeEnd, referenceResolver);

    if (refs === null) {
      return;
    }

    for (const ref of refs) {
      if (results.has(ref)) {
        continue;
      }

      results.add(ref);

      const closestTopLevel = closestNode(ref, isTopLevelStatement);
      // Avoid re-traversing the same top-level nodes since we know what the result will be.
      if (!closestTopLevel || traversedTopLevelNodes.has(closestTopLevel)) {
        continue;
      }

      // Keep searching, starting from the closest top-level node. We skip import declarations,
      // because we already know about them and they may put the search into an infinite loop.
      if (!ts.isImportDeclaration(closestTopLevel) &&
          isOutsideRange(
              excludeStart, excludeEnd, closestTopLevel.getStart(), closestTopLevel.getEnd())) {
        traversedTopLevelNodes.add(closestTopLevel);
        walk(closestTopLevel);
      }
    }
  })(rootNode);

  return results;
}

/**
 * Finds all the nodes referring to a specific node within the same file.
 * @param node Node whose references we're lookip for.
 * @param nodeLookup Map used to look up nodes based on their positions in a file.
 * @param excludeStart Start of a range that should be excluded from the results.
 * @param excludeEnd End of a range that should be excluded from the results.
 * @param referenceResolver
 */
function referencesToNodeWithinSameFile(
    node: ts.Identifier, nodeLookup: NodeLookup, excludeStart: number, excludeEnd: number,
    referenceResolver: ReferenceResolver): Set<ts.Node>|null {
  const offsets =
      referenceResolver.findSameFileReferences(node, node.getSourceFile().fileName)
          .filter(([start, end]) => isOutsideRange(excludeStart, excludeEnd, start, end));

  if (offsets.length > 0) {
    const nodes = offsetsToNodes(nodeLookup, offsets, new Set());

    if (nodes.size > 0) {
      return nodes;
    }
  }

  return null;
}

/**
 * Transforms a node so that any dynamic imports with relative file paths it contains are remapped
 * as if they were specified in a different file. If no transformations have occurred, the original
 * node will be returned.
 * @param targetFileName File name to which to remap the imports.
 * @param rootNode Node being transformed.
 */
function remapDynamicImports<T extends ts.Node>(targetFileName: string, rootNode: T): T {
  let hasChanged = false;
  const transformer: ts.TransformerFactory<ts.Node> = context => {
    return sourceFile => ts.visitNode(sourceFile, function walk(node: ts.Node): ts.Node {
      if (ts.isCallExpression(node) && node.expression.kind === ts.SyntaxKind.ImportKeyword &&
          node.arguments.length > 0 && ts.isStringLiteralLike(node.arguments[0]) &&
          node.arguments[0].text.startsWith('.')) {
        hasChanged = true;
        return context.factory.updateCallExpression(node, node.expression, node.typeArguments, [
          context.factory.createStringLiteral(
              remapRelativeImport(targetFileName, node.arguments[0])),
          ...node.arguments.slice(1)
        ]);
      }
      return ts.visitEachChild(node, walk, context);
    });
  };

  const result = ts.transform(rootNode, [transformer]).transformed[0] as T;
  return hasChanged ? result : rootNode;
}

/**
 * Checks whether a node is a statement at the top level of a file.
 * @param node Node to be checked.
 */
function isTopLevelStatement(node: ts.Node): node is ts.Node {
  return node.parent != null && ts.isSourceFile(node.parent);
}

/**
 * Asserts that a node is an identifier that might be referring to a symbol. This excludes
 * identifiers of named nodes like property assignments.
 * @param node Node to be checked.
 */
function isReferenceIdentifier(node: ts.Node): node is ts.Identifier {
  return ts.isIdentifier(node) &&
      (!ts.isPropertyAssignment(node.parent) && !ts.isParameter(node.parent) ||
       node.parent.name !== node);
}

/**
 * Checks whether a range is completely outside of another range.
 * @param excludeStart Start of the exclusion range.
 * @param excludeEnd End of the exclusion range.
 * @param start Start of the range that is being checked.
 * @param end End of the range that is being checked.
 */
function isOutsideRange(
    excludeStart: number, excludeEnd: number, start: number, end: number): boolean {
  return (start < excludeStart && end < excludeStart) || start > excludeEnd;
}

/**
 * Remaps the specifier of a relative import from its original location to a new one.
 * @param targetFileName Name of the file that the specifier will be moved to.
 * @param specifier Specifier whose path is being remapped.
 */
function remapRelativeImport(targetFileName: string, specifier: ts.StringLiteralLike): string {
  return getRelativeImportPath(
      targetFileName, join(dirname(specifier.getSourceFile().fileName), specifier.text));
}

/**
 * Whether a node is exported.
 * @param node Node to be checked.
 */
function isExported(node: ts.Node): node is ts.Node {
  return ts.canHaveModifiers(node) && node.modifiers ?
      node.modifiers.some(modifier => modifier.kind === ts.SyntaxKind.ExportKeyword) :
      false;
}

/**
 * Asserts that a node is an exportable declaration, which means that it can either be exported or
 * it can be safely copied into another file.
 * @param node Node to be checked.
 */
function isExportableDeclaration(node: ts.Node): node is ts.EnumDeclaration|ts.ClassDeclaration|
    ts.FunctionDeclaration|ts.InterfaceDeclaration|ts.TypeAliasDeclaration {
  return ts.isEnumDeclaration(node) || ts.isClassDeclaration(node) ||
      ts.isFunctionDeclaration(node) || ts.isInterfaceDeclaration(node) ||
      ts.isTypeAliasDeclaration(node);
}

/**
 * Gets the index after the last import in a file. Can be used to insert new code into the file.
 * @param sourceFile File in which to search for imports.
 */
function getLastImportEnd(sourceFile: ts.SourceFile): number {
  let index = 0;

  for (const statement of sourceFile.statements) {
    if (ts.isImportDeclaration(statement)) {
      index = Math.max(index, statement.getEnd());
    } else {
      break;
    }
  }

  return index;
}

/** Checks if any of the program's files has an import of a specific module. */
function hasImport(program: NgtscProgram, rootFileNames: string[], moduleName: string): boolean {
  const tsProgram = program.getTsProgram();
  const deepImportStart = moduleName + '/';

  for (const fileName of rootFileNames) {
    const sourceFile = tsProgram.getSourceFile(fileName);

    if (!sourceFile) {
      continue;
    }

    for (const statement of sourceFile.statements) {
      if (ts.isImportDeclaration(statement) && ts.isStringLiteralLike(statement.moduleSpecifier) &&
          (statement.moduleSpecifier.text === moduleName ||
           statement.moduleSpecifier.text.startsWith(deepImportStart))) {
        return true;
      }
    }
  }

  return false;
}