<commit_before>import {
  deprecationLogger,
  progressLogger,
  skippedOptionalDependencyLogger,
} from '@pnpm/core-loggers'
import PnpmError from '@pnpm/error'
import {
  Lockfile,
  PackageSnapshot,
  ResolvedDependencies,
} from '@pnpm/lockfile-types'
import {
  nameVerFromPkgSnapshot,
  packageIdFromSnapshot,
  pkgSnapshotToResolution,
} from '@pnpm/lockfile-utils'
import logger from '@pnpm/logger'
import packageIsInstallable from '@pnpm/package-is-installable'
import pickRegistryForPackage from '@pnpm/pick-registry-for-package'
import pkgIdToFilename from '@pnpm/pkgid-to-filename'
import {
  DirectoryResolution,
  PreferredVersions,
  Resolution,
  WorkspacePackages,
} from '@pnpm/resolver-base'
import {
  PackageFilesResponse,
  PackageResponse,
  StoreController,
} from '@pnpm/store-controller-types'
import {
  Dependencies,
  DependencyManifest,
  PackageManifest,
  PeerDependenciesMeta,
  ReadPackageHook,
  Registries,
} from '@pnpm/types'
import * as dp from 'dependency-path'
import path = require('path')
import exists = require('path-exists')
import R = require('ramda')
import semver = require('semver')
import encodePkgId from './encodePkgId'
import getNonDevWantedDependencies, { WantedDependency } from './getNonDevWantedDependencies'
import {
  createNodeId,
  nodeIdContainsSequence,
  splitNodeId,
} from './nodeIdUtils'
import wantedDepIsLocallyAvailable from './wantedDepIsLocallyAvailable'

const dependencyResolvedLogger = logger('_dependency_resolved')

export function nodeIdToParents (
  nodeId: string,
  resolvedPackagesByPackageId: ResolvedPackagesByPackageId
) {
  return splitNodeId(nodeId).slice(1)
    .map((pkgId) => {
      const { id, name, version } = resolvedPackagesByPackageId[pkgId]
      return { id, name, version }
    })
}

// child nodeId by child alias name in case of non-linked deps
export type ChildrenMap = {
  [alias: string]: string,
}

export type DependenciesTreeNode = {
  children: (() => ChildrenMap) | ChildrenMap,
  installable: boolean,
} & ({
  resolvedPackage: ResolvedPackage,
  depth: number,
} | {
  resolvedPackage: { version: string },
  depth: -1,
})

export interface DependenciesTree {
  // a node ID is the join of the package's keypath with a colon
  // E.g., a subdeps node ID which parent is `foo` will be
  // registry.npmjs.org/foo/1.0.0:registry.npmjs.org/bar/1.0.0
  [nodeId: string]: DependenciesTreeNode,
}

export interface ResolvedPackagesByPackageId {
  [packageId: string]: ResolvedPackage,
}

export interface LinkedDependency {
  isLinkedDependency: true,
  optional: boolean,
  dev: boolean,
  resolution: DirectoryResolution,
  pkgId: string,
  version: string,
  name: string,
  normalizedPref?: string,
  alias: string,
}

export interface PendingNode {
  alias: string,
  nodeId: string,
  resolvedPackage: ResolvedPackage,
  depth: number,
  installable: boolean,
}

export interface ChildrenByParentId {
  [parentId: string]: Array<{
    alias: string,
    pkgId: string,
  }>,
}

export interface ResolutionContext {
  alwaysTryWorkspacePackages?: boolean,
  defaultTag: string,
  dryRun: boolean,
  forceFullResolution: boolean,
  resolvedPackagesByPackageId: ResolvedPackagesByPackageId,
  outdatedDependencies: {[pkgId: string]: string},
  childrenByParentId: ChildrenByParentId,
  pendingNodes: PendingNode[],
  wantedLockfile: Lockfile,
  currentLockfile: Lockfile,
  linkWorkspacePackagesDepth: number,
  lockfileDir: string,
  storeController: StoreController,
  // the IDs of packages that are not installable
  skipped: Set<string>,
  dependenciesTree: DependenciesTree,
  force: boolean,
  prefix: string,
  readPackageHook?: ReadPackageHook,
  engineStrict: boolean,
  modulesDir: string,
  nodeVersion: string,
  pnpmVersion: string,
  registries: Registries,
  virtualStoreDir: string,
}

export type PkgAddress = {
  alias: string,
  depIsLinked: boolean,
  isNew: boolean,
  isLinkedDependency?: false,
  nodeId: string,
  pkgId: string,
  normalizedPref?: string, // is returned only for root dependencies
  installable: boolean,
  pkg: PackageManifest,
  version?: string,
  updated: boolean,
  useManifestInfoFromLockfile: boolean,
} & ({
  isLinkedDependency: true,
  version: string,
} | {
  isLinkedDependency: void,
})

export interface ResolvedPackage {
  id: string,
  resolution: Resolution,
  prod: boolean,
  dev: boolean,
  optional: boolean,
  fetchingFiles: () => Promise<PackageFilesResponse>,
  fetchingBundledManifest?: () => Promise<DependencyManifest>,
  filesIndexFile: string,
  finishing: () => Promise<void>,
  name: string,
  version: string,
  peerDependencies: Dependencies,
  optionalDependencies: Set<string>,
  hasBin: boolean,
  hasBundledDependencies: boolean,
  prepare: boolean,
  depPath: string,
  requiresBuild: boolean | undefined, // added to fix issue #1201
  additionalInfo: {
    deprecated?: string,
    peerDependencies?: Dependencies,
    peerDependenciesMeta?: PeerDependenciesMeta,
    bundleDependencies?: string[],
    bundledDependencies?: string[],
    engines?: {
      node?: string,
      npm?: string,
    },
    cpu?: string[],
    os?: string[],
  },
}

type ParentPkg = Pick<PkgAddress, 'nodeId' | 'installable' | 'pkgId'>

export default async function resolveDependencies (
  ctx: ResolutionContext,
  preferredVersions: PreferredVersions,
  wantedDependencies: Array<WantedDependency & { updateDepth?: number }>,
  options: {
    currentDepth: number,
    parentPkg: ParentPkg,
    // If the package has been updated, the dependencies
    // which were used by the previous version are passed
    // via this option
    preferredDependencies?: ResolvedDependencies,
    proceed: boolean,
    resolvedDependencies?: ResolvedDependencies,
    updateDepth: number,
    workspacePackages?: WorkspacePackages,
  }
): Promise<Array<PkgAddress | LinkedDependency>> {
  const extendedWantedDeps = getDepsToResolve(wantedDependencies, ctx.wantedLockfile, {
    preferredDependencies: options.preferredDependencies,
    prefix: ctx.prefix,
    proceed: options.proceed || ctx.forceFullResolution,
    registries: ctx.registries,
    resolvedDependencies: options.resolvedDependencies,
  })
  const resolveDepOpts = {
    currentDepth: options.currentDepth,
    parentPkg: options.parentPkg,
    preferredVersions,
    workspacePackages: options.workspacePackages,
  }
  const postponedResolutionsQueue = [] as Array<(preferredVersions: PreferredVersions) => Promise<void>>
  const resDeps = resolveDependencies.bind(null, ctx)
  const pkgAddresses = (
    await Promise.all(
      extendedWantedDeps
        .map(async (extendedWantedDep) => {
          const updateDepth = typeof extendedWantedDep.wantedDependency.updateDepth === 'number'
            ? extendedWantedDep.wantedDependency.updateDepth : options.updateDepth
          const resolveDependencyOpts: ResolveDependencyOptions = {
            ...resolveDepOpts,
            ...extendedWantedDep.infoFromLockfile,
            proceed: extendedWantedDep.proceed,
            update: options.currentDepth <= updateDepth,
            updateDepth,
          }
          const resolveDependencyResult = await resolveDependency(extendedWantedDep.wantedDependency, ctx, resolveDependencyOpts)

          if (!resolveDependencyResult) return null
          if (resolveDependencyResult.isLinkedDependency) {
            ctx.dependenciesTree[resolveDependencyResult.pkgId] = {
              children: {},
              depth: -1,
              installable: true,
              resolvedPackage: {
                version: resolveDependencyResult.version,
              },
            }
            return resolveDependencyResult
          }
          if (!resolveDependencyResult.isNew) return resolveDependencyResult

          const resolveChildren = async function (preferredVersions: PreferredVersions) {
            const resolvedPackage = ctx.resolvedPackagesByPackageId[resolveDependencyResult.pkgId]
            const resolvedDependencies = resolveDependencyResult.updated
              ? undefined
              : extendedWantedDep.infoFromLockfile?.resolvedDependencies
            const optionalDependencyNames = extendedWantedDep.infoFromLockfile?.optionalDependencyNames
            const workspacePackages = options.workspacePackages && ctx.linkWorkspacePackagesDepth > options.currentDepth
              ? options.workspacePackages : undefined
            const parentDependsOnPeer = Boolean(
              Object.keys(resolveDependencyOpts.dependencyLockfile?.peerDependencies ?? resolveDependencyResult.pkg.peerDependencies ?? {}).length
            )
            const children = await resDeps(preferredVersions,
              getWantedDependencies(resolveDependencyResult.pkg, {
                optionalDependencyNames,
                resolvedDependencies,
                useManifestInfoFromLockfile: resolveDependencyResult.useManifestInfoFromLockfile,
              }),
              {
                currentDepth: options.currentDepth + 1,
                parentPkg: resolveDependencyResult,
                preferredDependencies: resolveDependencyResult.updated
                  ? extendedWantedDep.infoFromLockfile?.resolvedDependencies
                  : undefined,
                // If the package is not linked, we should also gather information about its dependencies.
                // After linking the package we'll need to symlink its dependencies.
                proceed: !resolveDependencyResult.depIsLinked || parentDependsOnPeer,
                resolvedDependencies,
                updateDepth,
                workspacePackages,
              }
            ) as PkgAddress[]
            ctx.childrenByParentId[resolveDependencyResult.pkgId] = children.map((child) => ({
              alias: child.alias,
              pkgId: child.pkgId,
            }))
            ctx.dependenciesTree[resolveDependencyResult.nodeId] = {
              children: children.reduce((chn, child) => {
                chn[child.alias] = child.nodeId ?? child.pkgId
                return chn
              }, {}),
              depth: options.currentDepth,
              installable: resolveDependencyResult.installable,
              resolvedPackage,
            }
          }

          postponedResolutionsQueue.push(resolveChildren)

          return resolveDependencyResult
        })
    )
  )
  .filter(Boolean) as PkgAddress[]

  const newPreferredVersions = { ...preferredVersions }
  for (const { pkgId } of pkgAddresses) {
    const resolvedPackage = ctx.resolvedPackagesByPackageId[pkgId]
    if (!resolvedPackage) continue // This will happen only with linked dependencies
    if (!newPreferredVersions[resolvedPackage.name]) {
      newPreferredVersions[resolvedPackage.name] = {}
    }
    newPreferredVersions[resolvedPackage.name][resolvedPackage.version] = 'version'
  }
  await Promise.all(postponedResolutionsQueue.map((postponedResolution) => postponedResolution(newPreferredVersions)))

  return pkgAddresses
}

function getDepsToResolve (
  wantedDependencies: Array<WantedDependency & { updateDepth?: number }>,
  wantedLockfile: Lockfile,
  options: {
    preferredDependencies?: ResolvedDependencies,
    prefix: string,
    proceed: boolean,
    registries: Registries,
    resolvedDependencies?: ResolvedDependencies,
  }
) {
  const resolvedDependencies = options.resolvedDependencies ?? {}
  const preferredDependencies = options.preferredDependencies ?? {}
  const extendedWantedDeps = []
  // The only reason we resolve children in case the package depends on peers
  // is to get information about the existing dependencies, so that they can
  // be merged with the resolved peers.
  const proceedAll = options.proceed
  let allPeers = new Set<string>()
  for (const wantedDependency of wantedDependencies) {
    let reference = wantedDependency.alias && resolvedDependencies[wantedDependency.alias]
    let proceed = proceedAll

    // If dependencies that were used by the previous version of the package
    // satisfy the newer version's requirements, then pnpm tries to keep
    // the previous dependency.
    // So for example, if foo@1.0.0 had bar@1.0.0 as a dependency
    // and foo was updated to 1.1.0 which depends on bar ^1.0.0
    // then bar@1.0.0 can be reused for foo@1.1.0
    if (!reference && wantedDependency.alias && semver.validRange(wantedDependency.pref) !== null && // tslint:disable-line
      preferredDependencies[wantedDependency.alias] &&
      preferedSatisfiesWanted(
        preferredDependencies[wantedDependency.alias],
        wantedDependency as {alias: string, pref: string},
        wantedLockfile,
        {
          prefix: options.prefix,
        }
      )
    ) {
      proceed = true
      reference = preferredDependencies[wantedDependency.alias]
    }
    const infoFromLockfile = getInfoFromLockfile(wantedLockfile, options.registries, reference, wantedDependency.alias)
    if (
      !proceedAll &&
      infoFromLockfile?.dependencyLockfile?.peerDependencies
    ) {
      proceed = true
      Object.keys(infoFromLockfile.dependencyLockfile.peerDependencies).forEach((peerName) => {
        allPeers.add(peerName)
      })
    }
    extendedWantedDeps.push({
      infoFromLockfile,
      proceed,
      wantedDependency,
    })
  }
  if (!proceedAll && allPeers.size) {
    for (const extendedWantedDep of extendedWantedDeps) {
      if (!extendedWantedDep.proceed && allPeers.has(extendedWantedDep.wantedDependency.alias)) {
        extendedWantedDep.proceed = true
      }
    }
  }
  return extendedWantedDeps
}

function preferedSatisfiesWanted (
  preferredRef: string,
  wantedDep: {alias: string, pref: string},
  lockfile: Lockfile,
  opts: {
    prefix: string,
  }
) {
  const depPath = dp.refToRelative(preferredRef, wantedDep.alias)
  if (depPath === null) return false
  const pkgSnapshot = lockfile.packages?.[depPath]
  if (!pkgSnapshot) {
    logger.warn({
      message: `Could not find preferred package ${depPath} in lockfile`,
      prefix: opts.prefix,
    })
    return false
  }
  const { version } = nameVerFromPkgSnapshot(depPath, pkgSnapshot)
  return semver.satisfies(version, wantedDep.pref, true)
}

function getInfoFromLockfile (
  lockfile: Lockfile,
  registries: Registries,
  reference: string | undefined,
  pkgName: string | undefined
) {
  if (!reference || !pkgName) {
    return null
  }

  const depPath = dp.refToRelative(reference, pkgName)

  if (!depPath) {
    return null
  }

  let dependencyLockfile = lockfile.packages?.[depPath]

  if (dependencyLockfile) {
    if (dependencyLockfile.peerDependencies && dependencyLockfile.dependencies) {
      // This is done to guarantee that the dependency will be relinked with the
      // up-to-date peer dependencies
      // Covered by test: "peer dependency is grouped with dependency when peer is resolved not from a top dependency"
      const dependencies: Record<string, string> = {}
      for (const [depName, ref] of Object.entries(dependencyLockfile.dependencies ?? {})) {
        if (dependencyLockfile.peerDependencies[depName]) continue
        dependencies[depName] = ref
      }
      dependencyLockfile = {
        ...dependencyLockfile,
        dependencies,
      }
    }

    return {
      currentResolution: pkgSnapshotToResolution(depPath, dependencyLockfile, registries),
      dependencyLockfile,
      depPath,
      optionalDependencyNames: R.keys(dependencyLockfile.optionalDependencies),
      pkgId: packageIdFromSnapshot(depPath, dependencyLockfile, registries),
      resolvedDependencies: {
        ...dependencyLockfile.dependencies,
        ...dependencyLockfile.optionalDependencies,
      },
    }
  } else {
    return {
      depPath,
      pkgId: dp.tryGetPackageId(registries, depPath) || depPath, // Does it make sense to set pkgId when we're not sure?
    }
  }
}

type ResolveDependencyOptions = {
  currentDepth: number,
  currentResolution?: Resolution,
  depPath?: string,
  dependencyLockfile?: PackageSnapshot,
  parentPkg: ParentPkg,
  pkgId?: string,
  preferredVersions: PreferredVersions,
  proceed: boolean,
  update: boolean,
  updateDepth: number,
  workspacePackages?: WorkspacePackages,
}

async function resolveDependency (
  wantedDependency: WantedDependency,
  ctx: ResolutionContext,
  options: ResolveDependencyOptions
): Promise<PkgAddress | LinkedDependency | null> {
  const update = Boolean(
    options.update ||
    options.workspacePackages &&
    wantedDepIsLocallyAvailable(options.workspacePackages, wantedDependency, { defaultTag: ctx.defaultTag, registry: ctx.registries.default }))
  const proceed = update || options.proceed || !options.currentResolution
  const parentIsInstallable = options.parentPkg.installable === undefined || options.parentPkg.installable

  const currentLockfileContainsTheDep = options.depPath ? Boolean(ctx.currentLockfile.packages?.[options.depPath]) : undefined
  const depIsLinked = Boolean(
    // if package is not in `node_modules/.pnpm-lock.yaml`
    // we can safely assume that it doesn't exist in `node_modules`
    currentLockfileContainsTheDep &&
    options.depPath && options.dependencyLockfile &&
    await exists(path.join(ctx.virtualStoreDir, `${pkgIdToFilename(options.depPath, ctx.prefix)}/node_modules/${nameVerFromPkgSnapshot(options.depPath, options.dependencyLockfile).name}/package.json`)) &&
    (options.currentDepth > 0 || wantedDependency.alias && await exists(path.join(ctx.modulesDir, wantedDependency.alias))))

  if (!proceed && depIsLinked) {
    return null
  }

  let pkgResponse!: PackageResponse
  try {
    pkgResponse = await ctx.storeController.requestPackage(wantedDependency, {
      alwaysTryWorkspacePackages: ctx.alwaysTryWorkspacePackages,
      currentPackageId: options.pkgId,
      currentResolution: options.currentResolution,
      defaultTag: ctx.defaultTag,
      downloadPriority: -options.currentDepth,
      lockfileDir: ctx.lockfileDir,
      preferredVersions: options.preferredVersions,
      projectDir: options.currentDepth > 0 ? ctx.lockfileDir : ctx.prefix,
      registry: wantedDependency.alias && pickRegistryForPackage(ctx.registries, wantedDependency.alias) || ctx.registries.default,
      // Unfortunately, even when run with --lockfile-only, we need the *real* package.json
      // so fetching of the tarball cannot be ever avoided. Related issue: https://github.com/pnpm/pnpm/issues/1176
      skipFetch: false,
      update,
      workspacePackages: options.workspacePackages,
    })
  } catch (err) {
    if (wantedDependency.optional) {
      skippedOptionalDependencyLogger.debug({
        details: err.toString(),
        package: {
          name: wantedDependency.alias,
          pref: wantedDependency.pref,
          version: wantedDependency.alias ? wantedDependency.pref : undefined,
        },
        parents: nodeIdToParents(options.parentPkg.nodeId, ctx.resolvedPackagesByPackageId),
        prefix: ctx.prefix,
        reason: 'resolution_failure',
      })
      return null
    }
    err.pkgsStack = nodeIdToParents(options.parentPkg.nodeId, ctx.resolvedPackagesByPackageId)
    throw err
  }

  dependencyResolvedLogger.debug({
    resolution: pkgResponse.body.id,
    wanted: {
      dependentId: options.parentPkg.pkgId,
      name: wantedDependency.alias,
      rawSpec: wantedDependency.pref,
    },
  })

  pkgResponse.body.id = encodePkgId(pkgResponse.body.id)

  if (
    !pkgResponse.body.updated &&
    options.currentDepth === Math.max(0, options.updateDepth) &&
    depIsLinked && !ctx.force && !options.proceed
  ) {
    return null
  }

  if (pkgResponse.body.isLocal) {
    const manifest = pkgResponse.body.manifest || await pkgResponse.bundledManifest!() // tslint:disable-line:no-string-literal
    return {
      alias: wantedDependency.alias || manifest.name,
      dev: wantedDependency.dev,
      isLinkedDependency: true,
      name: manifest.name,
      normalizedPref: pkgResponse.body.normalizedPref,
      optional: wantedDependency.optional,
      pkgId: pkgResponse.body.id,
      resolution: pkgResponse.body.resolution,
      version: manifest.version,
    }
  }

  if (
    nodeIdContainsSequence(
      options.parentPkg.nodeId,
      options.parentPkg.pkgId,
      pkgResponse.body.id
    )
  ) {
    return null
  }

  let pkg: PackageManifest
  let useManifestInfoFromLockfile = false
  let prepare!: boolean
  let hasBin!: boolean
  if (
    !options.update && options.dependencyLockfile && options.depPath &&
    !pkgResponse.body.updated &&
    // peerDependencies field is also used for transitive peer dependencies which should not be linked
    // That's why we cannot omit reading package.json of such dependencies.
    // This can be removed if we implement something like peerDependenciesMeta.transitive: true
    !options.dependencyLockfile.peerDependencies
  ) {
    useManifestInfoFromLockfile = true
    prepare = options.dependencyLockfile.prepare === true
    hasBin = options.dependencyLockfile.hasBin === true
    pkg = Object.assign(
      nameVerFromPkgSnapshot(options.depPath, options.dependencyLockfile),
      options.dependencyLockfile
    )
  } else {
    // tslint:disable:no-string-literal
    pkg = ctx.readPackageHook
      ? ctx.readPackageHook(pkgResponse.body.manifest || await pkgResponse.bundledManifest!())
      : pkgResponse.body.manifest || await pkgResponse.bundledManifest!()

    prepare = Boolean(
      pkgResponse.body.resolvedVia === 'git-repository' &&
      typeof pkg.scripts?.prepare === 'string'
    )

    if (
      options.dependencyLockfile?.deprecated &&
      !pkgResponse.body.updated && !pkg.deprecated
    ) {
      pkg.deprecated = options.dependencyLockfile.deprecated
    }
    hasBin = Boolean(pkg.bin && !R.isEmpty(pkg.bin) || pkg.directories?.bin)
    // tslint:enable:no-string-literal
  }
  if (!pkg.name) { // TODO: don't fail on optional dependencies
    throw new PnpmError('MISSING_PACKAGE_NAME', `Can't install ${wantedDependency.pref}: Missing package name`)
  }
  if (options.currentDepth === 0 && pkgResponse.body.latest && pkgResponse.body.latest !== pkg.version) {
    ctx.outdatedDependencies[pkgResponse.body.id] = pkgResponse.body.latest
  }
  if (pkg.deprecated) {
    deprecationLogger.debug({
      deprecated: pkg.deprecated,
      depth: options.currentDepth,
      pkgId: pkgResponse.body.id,
      pkgName: pkg.name,
      pkgVersion: pkg.version,
      prefix: ctx.prefix,
    })
  }

  // using colon as it will never be used inside a package ID
  const nodeId = createNodeId(options.parentPkg.nodeId, pkgResponse.body.id)

  const currentIsInstallable = (
      ctx.force ||
      packageIsInstallable(pkgResponse.body.id, pkg, {
        engineStrict: ctx.engineStrict,
        lockfileDir: ctx.lockfileDir,
        nodeVersion: ctx.nodeVersion,
        optional: wantedDependency.optional,
        pnpmVersion: ctx.pnpmVersion,
      })
    )
  const installable = parentIsInstallable && currentIsInstallable !== false
  const isNew = !ctx.resolvedPackagesByPackageId[pkgResponse.body.id]

  if (isNew) {
    if (currentIsInstallable !== true || !parentIsInstallable) {
      ctx.skipped.add(pkgResponse.body.id)
    }
    progressLogger.debug({
      packageId: pkgResponse.body.id,
      requester: ctx.lockfileDir,
      status: 'resolved',
    })
    if (pkgResponse.files) {
      pkgResponse.files()
        .then((fetchResult: PackageFilesResponse) => {
          progressLogger.debug({
            packageId: pkgResponse.body.id,
            requester: ctx.lockfileDir,
            status: fetchResult.fromStore
              ? 'found_in_store' : 'fetched',
          })
        })
        .catch(() => {
          // Ignore
        })
    }

    ctx.resolvedPackagesByPackageId[pkgResponse.body.id] = getResolvedPackage({
      dependencyLockfile: options.dependencyLockfile,<commit_msg>refactor: resolve-dependencies<commit_after>import {
  deprecationLogger,
  progressLogger,
  skippedOptionalDependencyLogger,
} from '@pnpm/core-loggers'
import PnpmError from '@pnpm/error'
import {
  Lockfile,
  PackageSnapshot,
  ResolvedDependencies,
} from '@pnpm/lockfile-types'
import {
  nameVerFromPkgSnapshot,
  packageIdFromSnapshot,
  pkgSnapshotToResolution,
} from '@pnpm/lockfile-utils'
import logger from '@pnpm/logger'
import packageIsInstallable from '@pnpm/package-is-installable'
import pickRegistryForPackage from '@pnpm/pick-registry-for-package'
import pkgIdToFilename from '@pnpm/pkgid-to-filename'
import {
  DirectoryResolution,
  PreferredVersions,
  Resolution,
  WorkspacePackages,
} from '@pnpm/resolver-base'
import {
  PackageFilesResponse,
  PackageResponse,
  StoreController,
} from '@pnpm/store-controller-types'
import {
  Dependencies,
  DependencyManifest,
  PackageManifest,
  PeerDependenciesMeta,
  ReadPackageHook,
  Registries,
} from '@pnpm/types'
import * as dp from 'dependency-path'
import path = require('path')
import exists = require('path-exists')
import R = require('ramda')
import semver = require('semver')
import encodePkgId from './encodePkgId'
import getNonDevWantedDependencies, { WantedDependency } from './getNonDevWantedDependencies'
import {
  createNodeId,
  nodeIdContainsSequence,
  splitNodeId,
} from './nodeIdUtils'
import wantedDepIsLocallyAvailable from './wantedDepIsLocallyAvailable'

const dependencyResolvedLogger = logger('_dependency_resolved')

export function nodeIdToParents (
  nodeId: string,
  resolvedPackagesByPackageId: ResolvedPackagesByPackageId
) {
  return splitNodeId(nodeId).slice(1)
    .map((pkgId) => {
      const { id, name, version } = resolvedPackagesByPackageId[pkgId]
      return { id, name, version }
    })
}

// child nodeId by child alias name in case of non-linked deps
export type ChildrenMap = {
  [alias: string]: string,
}

export type DependenciesTreeNode = {
  children: (() => ChildrenMap) | ChildrenMap,
  installable: boolean,
} & ({
  resolvedPackage: ResolvedPackage,
  depth: number,
} | {
  resolvedPackage: { version: string },
  depth: -1,
})

export interface DependenciesTree {
  // a node ID is the join of the package's keypath with a colon
  // E.g., a subdeps node ID which parent is `foo` will be
  // registry.npmjs.org/foo/1.0.0:registry.npmjs.org/bar/1.0.0
  [nodeId: string]: DependenciesTreeNode,
}

export interface ResolvedPackagesByPackageId {
  [packageId: string]: ResolvedPackage,
}

export interface LinkedDependency {
  isLinkedDependency: true,
  optional: boolean,
  dev: boolean,
  resolution: DirectoryResolution,
  pkgId: string,
  version: string,
  name: string,
  normalizedPref?: string,
  alias: string,
}

export interface PendingNode {
  alias: string,
  nodeId: string,
  resolvedPackage: ResolvedPackage,
  depth: number,
  installable: boolean,
}

export interface ChildrenByParentId {
  [parentId: string]: Array<{
    alias: string,
    pkgId: string,
  }>,
}

export interface ResolutionContext {
  alwaysTryWorkspacePackages?: boolean,
  defaultTag: string,
  dryRun: boolean,
  forceFullResolution: boolean,
  resolvedPackagesByPackageId: ResolvedPackagesByPackageId,
  outdatedDependencies: {[pkgId: string]: string},
  childrenByParentId: ChildrenByParentId,
  pendingNodes: PendingNode[],
  wantedLockfile: Lockfile,
  currentLockfile: Lockfile,
  linkWorkspacePackagesDepth: number,
  lockfileDir: string,
  storeController: StoreController,
  // the IDs of packages that are not installable
  skipped: Set<string>,
  dependenciesTree: DependenciesTree,
  force: boolean,
  prefix: string,
  readPackageHook?: ReadPackageHook,
  engineStrict: boolean,
  modulesDir: string,
  nodeVersion: string,
  pnpmVersion: string,
  registries: Registries,
  virtualStoreDir: string,
}

export type PkgAddress = {
  alias: string,
  depIsLinked: boolean,
  isNew: boolean,
  isLinkedDependency?: false,
  nodeId: string,
  pkgId: string,
  normalizedPref?: string, // is returned only for root dependencies
  installable: boolean,
  pkg: PackageManifest,
  version?: string,
  updated: boolean,
  useManifestInfoFromLockfile: boolean,
} & ({
  isLinkedDependency: true,
  version: string,
} | {
  isLinkedDependency: void,
})

export interface ResolvedPackage {
  id: string,
  resolution: Resolution,
  prod: boolean,
  dev: boolean,
  optional: boolean,
  fetchingFiles: () => Promise<PackageFilesResponse>,
  fetchingBundledManifest?: () => Promise<DependencyManifest>,
  filesIndexFile: string,
  finishing: () => Promise<void>,
  name: string,
  version: string,
  peerDependencies: Dependencies,
  optionalDependencies: Set<string>,
  hasBin: boolean,
  hasBundledDependencies: boolean,
  prepare: boolean,
  depPath: string,
  requiresBuild: boolean | undefined, // added to fix issue #1201
  additionalInfo: {
    deprecated?: string,
    peerDependencies?: Dependencies,
    peerDependenciesMeta?: PeerDependenciesMeta,
    bundleDependencies?: string[],
    bundledDependencies?: string[],
    engines?: {
      node?: string,
      npm?: string,
    },
    cpu?: string[],
    os?: string[],
  },
}

type ParentPkg = Pick<PkgAddress, 'nodeId' | 'installable' | 'pkgId'>

export default async function resolveDependencies (
  ctx: ResolutionContext,
  preferredVersions: PreferredVersions,
  wantedDependencies: Array<WantedDependency & { updateDepth?: number }>,
  options: {
    currentDepth: number,
    parentPkg: ParentPkg,
    // If the package has been updated, the dependencies
    // which were used by the previous version are passed
    // via this option
    preferredDependencies?: ResolvedDependencies,
    proceed: boolean,
    resolvedDependencies?: ResolvedDependencies,
    updateDepth: number,
    workspacePackages?: WorkspacePackages,
  }
): Promise<Array<PkgAddress | LinkedDependency>> {
  const extendedWantedDeps = getDepsToResolve(wantedDependencies, ctx.wantedLockfile, {
    preferredDependencies: options.preferredDependencies,
    prefix: ctx.prefix,
    proceed: options.proceed || ctx.forceFullResolution,
    registries: ctx.registries,
    resolvedDependencies: options.resolvedDependencies,
  })
  const resolveDepOpts = {
    currentDepth: options.currentDepth,
    parentPkg: options.parentPkg,
    preferredVersions,
    workspacePackages: options.workspacePackages,
  }
  const postponedResolutionsQueue = [] as Array<(preferredVersions: PreferredVersions) => Promise<void>>
  const resDeps = resolveDependencies.bind(null, ctx)
  const pkgAddresses = (
    await Promise.all(
      extendedWantedDeps
        .map(async (extendedWantedDep) => {
          const updateDepth = typeof extendedWantedDep.wantedDependency.updateDepth === 'number'
            ? extendedWantedDep.wantedDependency.updateDepth : options.updateDepth
          const resolveDependencyOpts: ResolveDependencyOptions = {
            ...resolveDepOpts,
            currentPkg: extendedWantedDep.infoFromLockfile ?? undefined,
            proceed: extendedWantedDep.proceed,
            update: options.currentDepth <= updateDepth,
            updateDepth,
          }
          const resolveDependencyResult = await resolveDependency(extendedWantedDep.wantedDependency, ctx, resolveDependencyOpts)

          if (!resolveDependencyResult) return null
          if (resolveDependencyResult.isLinkedDependency) {
            ctx.dependenciesTree[resolveDependencyResult.pkgId] = {
              children: {},
              depth: -1,
              installable: true,
              resolvedPackage: {
                version: resolveDependencyResult.version,
              },
            }
            return resolveDependencyResult
          }
          if (!resolveDependencyResult.isNew) return resolveDependencyResult

          const resolveChildren = async function (preferredVersions: PreferredVersions) {
            const resolvedPackage = ctx.resolvedPackagesByPackageId[resolveDependencyResult.pkgId]
            const currentResolvedDependencies = extendedWantedDep.infoFromLockfile?.dependencyLockfile ? {
              ...extendedWantedDep.infoFromLockfile.dependencyLockfile.dependencies,
              ...extendedWantedDep.infoFromLockfile.dependencyLockfile.optionalDependencies,
            } : undefined
            const resolvedDependencies = resolveDependencyResult.updated
              ? undefined
              : currentResolvedDependencies
            const optionalDependencyNames = Object.keys(extendedWantedDep.infoFromLockfile?.dependencyLockfile?.optionalDependencies ?? {})
            const workspacePackages = options.workspacePackages && ctx.linkWorkspacePackagesDepth > options.currentDepth
              ? options.workspacePackages : undefined
            const parentDependsOnPeer = Boolean(
              Object.keys(resolveDependencyOpts.currentPkg?.dependencyLockfile?.peerDependencies ?? resolveDependencyResult.pkg.peerDependencies ?? {}).length
            )
            const children = await resDeps(preferredVersions,
              getWantedDependencies(resolveDependencyResult.pkg, {
                optionalDependencyNames,
                resolvedDependencies,
                useManifestInfoFromLockfile: resolveDependencyResult.useManifestInfoFromLockfile,
              }),
              {
                currentDepth: options.currentDepth + 1,
                parentPkg: resolveDependencyResult,
                preferredDependencies: resolveDependencyResult.updated
                  ? currentResolvedDependencies
                  : undefined,
                // If the package is not linked, we should also gather information about its dependencies.
                // After linking the package we'll need to symlink its dependencies.
                proceed: !resolveDependencyResult.depIsLinked || parentDependsOnPeer,
                resolvedDependencies,
                updateDepth,
                workspacePackages,
              }
            ) as PkgAddress[]
            ctx.childrenByParentId[resolveDependencyResult.pkgId] = children.map((child) => ({
              alias: child.alias,
              pkgId: child.pkgId,
            }))
            ctx.dependenciesTree[resolveDependencyResult.nodeId] = {
              children: children.reduce((chn, child) => {
                chn[child.alias] = child.nodeId ?? child.pkgId
                return chn
              }, {}),
              depth: options.currentDepth,
              installable: resolveDependencyResult.installable,
              resolvedPackage,
            }
          }

          postponedResolutionsQueue.push(resolveChildren)

          return resolveDependencyResult
        })
    )
  )
  .filter(Boolean) as PkgAddress[]

  const newPreferredVersions = { ...preferredVersions }
  for (const { pkgId } of pkgAddresses) {
    const resolvedPackage = ctx.resolvedPackagesByPackageId[pkgId]
    if (!resolvedPackage) continue // This will happen only with linked dependencies
    if (!newPreferredVersions[resolvedPackage.name]) {
      newPreferredVersions[resolvedPackage.name] = {}
    }
    newPreferredVersions[resolvedPackage.name][resolvedPackage.version] = 'version'
  }
  await Promise.all(postponedResolutionsQueue.map((postponedResolution) => postponedResolution(newPreferredVersions)))

  return pkgAddresses
}

function getDepsToResolve (
  wantedDependencies: Array<WantedDependency & { updateDepth?: number }>,
  wantedLockfile: Lockfile,
  options: {
    preferredDependencies?: ResolvedDependencies,
    prefix: string,
    proceed: boolean,
    registries: Registries,
    resolvedDependencies?: ResolvedDependencies,
  }
) {
  const resolvedDependencies = options.resolvedDependencies ?? {}
  const preferredDependencies = options.preferredDependencies ?? {}
  const extendedWantedDeps = []
  // The only reason we resolve children in case the package depends on peers
  // is to get information about the existing dependencies, so that they can
  // be merged with the resolved peers.
  const proceedAll = options.proceed
  let allPeers = new Set<string>()
  for (const wantedDependency of wantedDependencies) {
    let reference = wantedDependency.alias && resolvedDependencies[wantedDependency.alias]
    let proceed = proceedAll

    // If dependencies that were used by the previous version of the package
    // satisfy the newer version's requirements, then pnpm tries to keep
    // the previous dependency.
    // So for example, if foo@1.0.0 had bar@1.0.0 as a dependency
    // and foo was updated to 1.1.0 which depends on bar ^1.0.0
    // then bar@1.0.0 can be reused for foo@1.1.0
    if (!reference && wantedDependency.alias && semver.validRange(wantedDependency.pref) !== null && // tslint:disable-line
      preferredDependencies[wantedDependency.alias] &&
      preferedSatisfiesWanted(
        preferredDependencies[wantedDependency.alias],
        wantedDependency as {alias: string, pref: string},
        wantedLockfile,
        {
          prefix: options.prefix,
        }
      )
    ) {
      proceed = true
      reference = preferredDependencies[wantedDependency.alias]
    }
    const infoFromLockfile = getInfoFromLockfile(wantedLockfile, options.registries, reference, wantedDependency.alias)
    if (
      !proceedAll &&
      infoFromLockfile?.dependencyLockfile?.peerDependencies
    ) {
      proceed = true
      Object.keys(infoFromLockfile.dependencyLockfile.peerDependencies).forEach((peerName) => {
        allPeers.add(peerName)
      })
    }
    extendedWantedDeps.push({
      infoFromLockfile,
      proceed,
      wantedDependency,
    })
  }
  if (!proceedAll && allPeers.size) {
    for (const extendedWantedDep of extendedWantedDeps) {
      if (!extendedWantedDep.proceed && allPeers.has(extendedWantedDep.wantedDependency.alias)) {
        extendedWantedDep.proceed = true
      }
    }
  }
  return extendedWantedDeps
}

function preferedSatisfiesWanted (
  preferredRef: string,
  wantedDep: {alias: string, pref: string},
  lockfile: Lockfile,
  opts: {
    prefix: string,
  }
) {
  const depPath = dp.refToRelative(preferredRef, wantedDep.alias)
  if (depPath === null) return false
  const pkgSnapshot = lockfile.packages?.[depPath]
  if (!pkgSnapshot) {
    logger.warn({
      message: `Could not find preferred package ${depPath} in lockfile`,
      prefix: opts.prefix,
    })
    return false
  }
  const { version } = nameVerFromPkgSnapshot(depPath, pkgSnapshot)
  return semver.satisfies(version, wantedDep.pref, true)
}

function getInfoFromLockfile (
  lockfile: Lockfile,
  registries: Registries,
  reference: string | undefined,
  pkgName: string | undefined
) {
  if (!reference || !pkgName) {
    return null
  }

  const depPath = dp.refToRelative(reference, pkgName)

  if (!depPath) {
    return null
  }

  let dependencyLockfile = lockfile.packages?.[depPath]

  if (dependencyLockfile) {
    if (dependencyLockfile.peerDependencies && dependencyLockfile.dependencies) {
      // This is done to guarantee that the dependency will be relinked with the
      // up-to-date peer dependencies
      // Covered by test: "peer dependency is grouped with dependency when peer is resolved not from a top dependency"
      const dependencies: Record<string, string> = {}
      for (const [depName, ref] of Object.entries(dependencyLockfile.dependencies ?? {})) {
        if (dependencyLockfile.peerDependencies[depName]) continue
        dependencies[depName] = ref
      }
      dependencyLockfile = {
        ...dependencyLockfile,
        dependencies,
      }
    }

    return {
      dependencyLockfile,
      depPath,
      pkgId: packageIdFromSnapshot(depPath, dependencyLockfile, registries),
      resolution: pkgSnapshotToResolution(depPath, dependencyLockfile, registries),
    }
  } else {
    return {
      depPath,
      pkgId: dp.tryGetPackageId(registries, depPath) || depPath, // Does it make sense to set pkgId when we're not sure?
    }
  }
}

type ResolveDependencyOptions = {
  currentDepth: number,
  currentPkg?: {
    depPath?: string,
    pkgId?: string,
    resolution?: Resolution,
    dependencyLockfile?: PackageSnapshot,
  },
  parentPkg: ParentPkg,
  preferredVersions: PreferredVersions,
  proceed: boolean,
  update: boolean,
  updateDepth: number,
  workspacePackages?: WorkspacePackages,
}

async function resolveDependency (
  wantedDependency: WantedDependency,
  ctx: ResolutionContext,
  options: ResolveDependencyOptions
): Promise<PkgAddress | LinkedDependency | null> {
  const update = Boolean(
    options.update ||
    options.workspacePackages &&
    wantedDepIsLocallyAvailable(options.workspacePackages, wantedDependency, { defaultTag: ctx.defaultTag, registry: ctx.registries.default }))
  const currentPkg = options.currentPkg ?? {}
  const proceed = update || options.proceed || !currentPkg.resolution
  const parentIsInstallable = options.parentPkg.installable === undefined || options.parentPkg.installable

  const currentLockfileContainsTheDep = currentPkg.depPath
    ? Boolean(ctx.currentLockfile.packages?.[currentPkg.depPath]) : undefined
  const depIsLinked = Boolean(
    // if package is not in `node_modules/.pnpm-lock.yaml`
    // we can safely assume that it doesn't exist in `node_modules`
    currentLockfileContainsTheDep &&
    currentPkg.depPath && currentPkg.dependencyLockfile &&
    await exists(path.join(ctx.virtualStoreDir, `${pkgIdToFilename(currentPkg.depPath, ctx.prefix)}/node_modules/${nameVerFromPkgSnapshot(currentPkg.depPath, currentPkg.dependencyLockfile).name}/package.json`)) &&
    (options.currentDepth > 0 || wantedDependency.alias && await exists(path.join(ctx.modulesDir, wantedDependency.alias))))

  if (!proceed && depIsLinked) {
    return null
  }

  let pkgResponse!: PackageResponse
  try {
    pkgResponse = await ctx.storeController.requestPackage(wantedDependency, {
      alwaysTryWorkspacePackages: ctx.alwaysTryWorkspacePackages,
      currentPackageId: currentPkg.pkgId,
      currentResolution: currentPkg.resolution,
      defaultTag: ctx.defaultTag,
      downloadPriority: -options.currentDepth,
      lockfileDir: ctx.lockfileDir,
      preferredVersions: options.preferredVersions,
      projectDir: options.currentDepth > 0 ? ctx.lockfileDir : ctx.prefix,
      registry: wantedDependency.alias && pickRegistryForPackage(ctx.registries, wantedDependency.alias) || ctx.registries.default,
      // Unfortunately, even when run with --lockfile-only, we need the *real* package.json
      // so fetching of the tarball cannot be ever avoided. Related issue: https://github.com/pnpm/pnpm/issues/1176
      skipFetch: false,
      update,
      workspacePackages: options.workspacePackages,
    })
  } catch (err) {
    if (wantedDependency.optional) {
      skippedOptionalDependencyLogger.debug({
        details: err.toString(),
        package: {
          name: wantedDependency.alias,
          pref: wantedDependency.pref,
          version: wantedDependency.alias ? wantedDependency.pref : undefined,
        },
        parents: nodeIdToParents(options.parentPkg.nodeId, ctx.resolvedPackagesByPackageId),
        prefix: ctx.prefix,
        reason: 'resolution_failure',
      })
      return null
    }
    err.pkgsStack = nodeIdToParents(options.parentPkg.nodeId, ctx.resolvedPackagesByPackageId)
    throw err
  }

  dependencyResolvedLogger.debug({
    resolution: pkgResponse.body.id,
    wanted: {
      dependentId: options.parentPkg.pkgId,
      name: wantedDependency.alias,
      rawSpec: wantedDependency.pref,
    },
  })

  pkgResponse.body.id = encodePkgId(pkgResponse.body.id)

  if (
    !pkgResponse.body.updated &&
    options.currentDepth === Math.max(0, options.updateDepth) &&
    depIsLinked && !ctx.force && !options.proceed
  ) {
    return null
  }

  if (pkgResponse.body.isLocal) {
    const manifest = pkgResponse.body.manifest || await pkgResponse.bundledManifest!() // tslint:disable-line:no-string-literal
    return {
      alias: wantedDependency.alias || manifest.name,
      dev: wantedDependency.dev,
      isLinkedDependency: true,
      name: manifest.name,
      normalizedPref: pkgResponse.body.normalizedPref,
      optional: wantedDependency.optional,
      pkgId: pkgResponse.body.id,
      resolution: pkgResponse.body.resolution,
      version: manifest.version,
    }
  }

  if (
    nodeIdContainsSequence(
      options.parentPkg.nodeId,
      options.parentPkg.pkgId,
      pkgResponse.body.id
    )
  ) {
    return null
  }

  let pkg: PackageManifest
  let useManifestInfoFromLockfile = false
  let prepare!: boolean
  let hasBin!: boolean
  if (
    !options.update && currentPkg.dependencyLockfile && currentPkg.depPath &&
    !pkgResponse.body.updated &&
    // peerDependencies field is also used for transitive peer dependencies which should not be linked
    // That's why we cannot omit reading package.json of such dependencies.
    // This can be removed if we implement something like peerDependenciesMeta.transitive: true
    !currentPkg.dependencyLockfile.peerDependencies
  ) {
    useManifestInfoFromLockfile = true
    prepare = currentPkg.dependencyLockfile.prepare === true
    hasBin = currentPkg.dependencyLockfile.hasBin === true
    pkg = Object.assign(
      nameVerFromPkgSnapshot(currentPkg.depPath, currentPkg.dependencyLockfile),
      currentPkg.dependencyLockfile
    )
  } else {
    // tslint:disable:no-string-literal
    pkg = ctx.readPackageHook
      ? ctx.readPackageHook(pkgResponse.body.manifest || await pkgResponse.bundledManifest!())
      : pkgResponse.body.manifest || await pkgResponse.bundledManifest!()

    prepare = Boolean(
      pkgResponse.body.resolvedVia === 'git-repository' &&
      typeof pkg.scripts?.prepare === 'string'
    )

    if (
      currentPkg.dependencyLockfile?.deprecated &&
      !pkgResponse.body.updated && !pkg.deprecated
    ) {
      pkg.deprecated = currentPkg.dependencyLockfile.deprecated
    }
    hasBin = Boolean(pkg.bin && !R.isEmpty(pkg.bin) || pkg.directories?.bin)
    // tslint:enable:no-string-literal
  }
  if (!pkg.name) { // TODO: don't fail on optional dependencies
    throw new PnpmError('MISSING_PACKAGE_NAME', `Can't install ${wantedDependency.pref}: Missing package name`)
  }
  if (options.currentDepth === 0 && pkgResponse.body.latest && pkgResponse.body.latest !== pkg.version) {
    ctx.outdatedDependencies[pkgResponse.body.id] = pkgResponse.body.latest
  }
  if (pkg.deprecated) {
    deprecationLogger.debug({
      deprecated: pkg.deprecated,
      depth: options.currentDepth,
      pkgId: pkgResponse.body.id,
      pkgName: pkg.name,
      pkgVersion: pkg.version,
      prefix: ctx.prefix,
    })
  }

  // using colon as it will never be used inside a package ID
  const nodeId = createNodeId(options.parentPkg.nodeId, pkgResponse.body.id)

  const currentIsInstallable = (
      ctx.force ||
      packageIsInstallable(pkgResponse.body.id, pkg, {
        engineStrict: ctx.engineStrict,
        lockfileDir: ctx.lockfileDir,
        nodeVersion: ctx.nodeVersion,
        optional: wantedDependency.optional,
        pnpmVersion: ctx.pnpmVersion,
      })
    )
  const installable = parentIsInstallable && currentIsInstallable !== false
  const isNew = !ctx.resolvedPackagesByPackageId[pkgResponse.body.id]

  if (isNew) {
    if (currentIsInstallable !== true || !parentIsInstallable) {
      ctx.skipped.add(pkgResponse.body.id)
    }
    progressLogger.debug({
      packageId: pkgResponse.body.id,
      requester: ctx.lockfileDir,
      status: 'resolved',
    })
    if (pkgResponse.files) {
      pkgResponse.files()
        .then((fetchResult: PackageFilesResponse) => {
          progressLogger.debug({
            packageId: pkgResponse.body.id,
            requester: ctx.lockfileDir,
            status: fetchResult.fromStore
              ? 'found_in_store' : 'fetched',
          })
        })
        .catch(() => {
          // Ignore
        })
    }

    ctx.resolvedPackagesByPackageId[pkgResponse.body.id] = getResolvedPackage({
      dependencyLockfile: currentPkg.dependencyLockfile,
{'fraction_non_alphanumeric': 0.09391297092077266, 'fraction_numerical': 0.0016688222287120865, 'mean_word_length': 3.396460014673514, 'pattern_counts': {'":': 0, '<': 37, '<?xml version=': 0, '>': 67, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6984033', 'n_tokens_mistral': 13588, 'n_tokens_neox': 13176, 'n_words': 2977}