function addMissingPaths(tree: Tree, routingModulePath: Path, targetFile: Path): void {
  const targetDir = dirname(targetFile);
  const relativePath = targetDir.replace(dirname(routingModulePath), '');
  const existingPathEnd = targetDir.indexOf(relativePath);
  let existingPath = normalize(targetDir.slice(0, existingPathEnd));
  const pathsToCheck = dirsToRoutePaths(relativePath);

  for (let i = 0; i < pathsToCheck.length; i++) {
    const routePathToCheck = pathsToCheck[i];
    const fullPathToCheck = join(existingPath, routePathToCheck);
    const pathPredicates = routePredicatesFromPath(routingModulePath, fullPathToCheck);
    let routesArray = findRoutesArray(tree, routingModulePath);

    let route = findRouteWithPath(routesArray, pathPredicates);
    if (!route) {
      const routesArrayToAddTo = getParentRouteChildren(routesArray, routingModulePath, fullPathToCheck);
      addRoute(tree, routingModulePath, routesArrayToAddTo, generatePathRoute(routePathToCheck));
      routesArray = findRoutesArray(tree, routingModulePath);
      route = findRouteWithPath(routesArray, pathPredicates) as ts.ObjectLiteralExpression;
    }

    const allChecked = i === pathsToCheck.length - 1;
    if (allChecked) {
      return;
    }

    existingPath = fullPathToCheck;
    if (!getRouteChildren(route)) {
      addObjectProperty(tree, getSourceFile(tree, routingModulePath), route, 'children: []');
    }
  }
}

export function importPath(from: Path, to: Path): string {
  const relativePath = relative(dirname(from), dirname(to));

  if (relativePath.startsWith('.')) {
    return relativePath;
  }

  if (!relativePath) {
    return generateCurrentDirImport(basename(to));
  }

  return generateCurrentDirImport(join(relativePath, basename(to)));
}

export function findModuleFromOptions(host: Tree, options: ModuleOptions): Path | undefined {
  if (options.hasOwnProperty('skipImport') && options.skipImport) {
    return undefined;
  }

  const moduleExt = options.moduleExt || MODULE_EXT;
  const routingModuleExt = options.routingModuleExt || ROUTING_MODULE_EXT;

  if (!options.module) {
    const pathToCheck = (options.path || '')
      + (options.flat ? '' : '/' + strings.dasherize(options.name));

    return normalize(findModule(host, pathToCheck, moduleExt, routingModuleExt));
  } else {
    const modulePath = normalize(`/${options.path}/${options.module}`);
    const componentPath = normalize(`/${options.path}/${options.name}`);
    const moduleBaseName = normalize(modulePath).split('/').pop();

    const candidateSet = new Set<Path>([
      normalize(options.path || '/'),
    ]);

    for (let dir = modulePath; dir != NormalizedRoot; dir = dirname(dir)) {
      candidateSet.add(dir);
    }
    for (let dir = componentPath; dir != NormalizedRoot; dir = dirname(dir)) {
      candidateSet.add(dir);
    }

    const candidatesDirs = [...candidateSet].sort((a, b) => b.length - a.length);
    for (const c of candidatesDirs) {
      const candidateFiles = [
        '',
        `${moduleBaseName}.ts`,
        `${moduleBaseName}${moduleExt}`,
      ].map(x => join(c, x));

      for (const sc of candidateFiles) {
        if (host.exists(sc)) {
          return normalize(sc);
        }
      }
    }

    throw new Error(
      `Specified module '${options.module}' does not exist.\n`
        + `Looked in the following directories:\n    ${candidatesDirs.join('\n    ')}`,
    );
  }
}

function addModuleRoute(
  tree: Tree,
  moduleDeclaration: ts.ClassDeclaration,
  modulePath: Path,
  routingModulePath: Path,
): void {
  const moduleDir = dirname(modulePath);
  if (isRootPlaygroundModule(moduleDir)) {
    return;
  }

  const routePredicates = routePredicatesFromPath(routingModulePath, moduleDir);
  let route = findRouteWithPath(findRoutesArray(tree, routingModulePath), routePredicates);
  if (!route) {
    addMissingChildRoutes(tree, routingModulePath, modulePath);
    route = findRouteWithPath(findRoutesArray(tree, routingModulePath), routePredicates) as ts.ObjectLiteralExpression;
  }

  if (getRouteLazyModule(route)) {
    return;
  }

  const moduleClassName = (moduleDeclaration.name as ts.Identifier).getText();
  const lazyModulePath = generateLazyModulePath(routingModulePath, modulePath, moduleClassName);
  const loadChildren = `loadChildren: '${lazyModulePath}'`;
  addObjectProperty(tree, getSourceFile(tree, routingModulePath), route, loadChildren);
}

function getBootstrapComponentPath(
  host: Tree,
  project: WorkspaceProject,
): string {
  const projectTargets = getProjectTargets(project);
  if (!projectTargets.build) {
    throw targetBuildNotFoundError();
  }

  const mainPath = projectTargets.build.options.main;
  const modulePath = getAppModulePath(host, mainPath);
  const moduleSource = getSourceFile(host, modulePath);

  const metadataNode = getDecoratorMetadata(moduleSource, 'NgModule', '@angular/core')[0];
  const bootstrapProperty = getMetadataProperty(metadataNode, 'bootstrap');

  const arrLiteral = (bootstrapProperty as ts.PropertyAssignment)
    .initializer as ts.ArrayLiteralExpression;

  const componentSymbol = arrLiteral.elements[0].getText();

  const relativePath = getSourceNodes(moduleSource)
    .filter(node => node.kind === ts.SyntaxKind.ImportDeclaration)
    .filter(imp => {
      return findNode(imp, ts.SyntaxKind.Identifier, componentSymbol);
    })
    .map((imp: ts.ImportDeclaration) => {
      const pathStringLiteral = imp.moduleSpecifier as ts.StringLiteral;

      return pathStringLiteral.text;
    })[0];

  return join(dirname(normalize(modulePath)), relativePath + '.ts');
}

function addComponentRoute(
  tree: Tree,
  componentDeclarations: ts.ClassDeclaration[],
  modulePath: Path,
  context: SchematicContext,
  componentPath: Path,
): void {
  const routingModulePath = findRoutingModule(tree, dirname(componentPath));
  if (!routingModulePath) {
    throw new SchematicsException(`Can't find routing module for module ${modulePath}.`);
  }
  if (componentDeclarations.length > 1) {
    context.logger.warn(`Found more than one component declaration in ${componentPath}. ` +
      'Route will be created only for the first one.\n' +
      'Move all helper components which don\'t need own routes to sub directory without routing module in it.');
  }

  const componentClassName = (componentDeclarations[0].name as ts.Identifier).getText();
  const routes = findRoutesArray(tree, routingModulePath);

  if (findRoute(routes, componentRoutePredicate.bind(null, componentClassName))) {
    return;
  }

  const routingImport = importPath(routingModulePath, componentPath);
  const routePath = isInPlaygroundRoot(componentPath) ? '' : removeExtension(componentPath);
  const route = generateComponentRoute(routePath, componentClassName);
  addRoute(tree, routingModulePath, routes, route, componentClassName, routingImport);
}

export function findRoutingModule(tree: Tree, path: Path): Path | undefined {
  if (isOutsidePlayground(path)) {
    return;
  }

  const moduleFile = tree.getDir(path).subfiles.find(isRoutingModule);
  return moduleFile ? join(path, moduleFile) : findRoutingModule(tree, dirname(path));
}

export function routePredicatesFromPath(routingModulePath: Path, targetDirPath: Path): RoutePredicate[] {
  const routingModuleDir = dirname(routingModulePath);
  if (isRootPlaygroundModule(routingModuleDir)) {
    return [rootRoutePredicate(targetDirPath)];
  }

  const predicates: RoutePredicate[] = [];
  if (isBasePlaygroundModule(routingModuleDir)) {
    predicates.push(baseComponentPredicate(targetDirPath));
  }
  const relativeToRoutingModule = targetDirPath.replace(dirname(routingModulePath), '');
  const routePaths = dirsToRoutePaths(relativeToRoutingModule);
  for (const path of routePaths) {
    predicates.push((route: ts.ObjectLiteralExpression) => pathRoutePredicate(path, route));
  }

  return predicates;
}

export function parseName(path: string, name: string): Location {
  const nameWithoutPath = basename(name as Path);
  const namePath = dirname((path + '/' + name) as Path);

  return {
    name: nameWithoutPath,
    path: normalize('/' + namePath),
  };
}

function wrapHtmlFileTemplate(tree: Tree, templateDescriptor: TemplateDescriptor) {
  const { templateUrlProp, componentPath, template } = templateDescriptor;

  const templateUrl = (templateUrlProp.initializer as ts.StringLiteral).text;
  const dir = dirname(normalize(componentPath));
  const templatePath = join(dir, templateUrl);

  writeText(tree, templatePath, wrapHtmlFileTemplateInLayout(template));
}