Package Resolution in TypeScript: A Dependency Graph Challenge

Package resolution is a fundamental aspect of modern JavaScript development, especially when using tools like npm or yarn. This challenge asks you to model the core logic of package resolution in TypeScript, focusing on dependency graph creation and version matching. Successfully completing this challenge will demonstrate your understanding of data structures, algorithms, and TypeScript's type system.

Problem Description

You are tasked with creating a TypeScript module that can resolve dependencies for a given package. The module should take a package manifest (represented as a TypeScript object) and a version constraint, and return a resolved dependency graph. The dependency graph should represent the resolved versions of all dependencies, respecting version constraints.

What needs to be achieved:

1. Define Data Structures: Create TypeScript types to represent a package manifest, a dependency, and a resolved dependency.
2. Parse Version Constraints: Implement a function to parse version constraints (e.g., "1.2.3", ">=1.0.0", "<2.0.0", "^1.2.0", "~1.1.0"). For simplicity, assume constraints are always valid.
3. Resolve Dependencies: Implement a function that takes a package manifest and a version constraint for the top-level package, and recursively resolves all dependencies, respecting their version constraints.
4. Create Dependency Graph: The output should be a dependency graph represented as a map where keys are package names and values are the resolved versions.

Key Requirements:

• Version Matching: The resolution process must adhere to semantic versioning (semver) principles for version matching. For this challenge, you only need to support ^ (caret) and ~ (tilde) version ranges. Exact versions should also be supported.
• Recursive Resolution: Dependencies can have their own dependencies, so the resolution process must be recursive.
• Circular Dependency Detection: The resolution process should detect and prevent circular dependencies. If a circular dependency is detected, throw an error.
• Type Safety: Utilize TypeScript's type system to ensure type safety throughout the module.

Expected Behavior:

The resolveDependencies function should return a map of package names to resolved versions. If a circular dependency is detected, it should throw an Error with a descriptive message.

Edge Cases to Consider:

• Empty dependency lists.
• Dependencies with no version constraints (assume latest version).
• Circular dependencies.
• Nested dependencies with complex version constraints.

Examples

Example 1:

Input:
packageManifest = {
  name: "my-app",
  version: "1.0.0",
  dependencies: {
    "package-a": "1.2.3",
    "package-b": "^2.0.0"
  }
}
versionConstraint = "1.0.0"

Output:
{
  "my-app": "1.0.0",
  "package-a": "1.2.3",
  "package-b": "2.0.0"
}
Explanation: The top-level package is "my-app" version "1.0.0". "package-a" has a specific version constraint "1.2.3", so that version is used. "package-b" has a caret constraint "^2.0.0", so the latest compatible version (2.0.0) is used.

Example 2:

Input:
packageManifest = {
  name: "my-app",
  version: "1.0.0",
  dependencies: {
    "package-a": "~1.1.0",
    "package-b": "package-a"
  }
}
versionConstraint = "1.0.0"

Output:
{
  "my-app": "1.0.0",
  "package-a": "1.1.0",
  "package-b": "1.1.0"
}
Explanation: "my-app" is version "1.0.0". "package-a" has a tilde constraint "~1.1.0", so version "1.1.0" is used. "package-b" depends on "package-a", so it also resolves to "1.1.0".

Example 3: (Circular Dependency)

Input:
packageManifest = {
  name: "my-app",
  version: "1.0.0",
  dependencies: {
    "package-a": "package-b"
  }
}
packageManifestB = {
  name: "package-b",
  version: "1.0.0",
  dependencies: {
    "package-a": "package-b"
  }
}
versionConstraint = "1.0.0"

Output:
Throws Error: "Circular dependency detected: my-app -> package-b -> package-a -> my-app"
Explanation:  "my-app" depends on "package-b", which depends on "package-a", which depends on "my-app", creating a circular dependency.

Constraints

• Version Constraint Parsing: Only support ^ (caret) and ~ (tilde) version ranges, and exact versions.
• Circular Dependency Detection: The algorithm must detect circular dependencies within a reasonable number of iterations (e.g., 100) to prevent infinite loops.
• Input Size: The package manifest and dependency graph will not exceed 100 packages.
• Performance: The resolution process should complete within a reasonable time (e.g., under 1 second) for typical package manifests.

Notes

• You don't need to implement a full-fledged semver library. Focus on the core logic of resolving dependencies based on the specified constraints.
• Consider using a Set to keep track of visited packages during the recursive resolution process to detect circular dependencies.
• Think about how to handle dependencies that refer to other dependencies by name instead of version numbers (as shown in Example 3). For this challenge, assume that if a dependency is specified by name, it should be resolved recursively.
• Error handling is important. Provide clear and informative error messages when circular dependencies are detected.
• Prioritize code clarity and type safety over extreme optimization.