Problem

You have a monorepo containing multiple packages.

Some packages have generated files. Whenever a package's TypeScript source code changes, that package needs to regenerate its files.

Also, if a package depends on another package whose source code changed, it needs to regenerate too.

Your task is to find all packages that need regeneration.

Package Structure

Each package has:

interface Package {
name: string;
srcPath: string;
deps: string[];
}

For example:

const packages: Package[] = [
{
name: "@acme/auth",
srcPath: "packages/auth/",
deps: ["@acme/shared"]
},
{
name: "@acme/payments",
srcPath: "packages/payments/",
deps: ["@acme/shared", "@acme/currency"]
},
{
name: "@acme/ui",
srcPath: "packages/ui/",
deps: ["@acme/shared"]
},
{
name: "@acme/shared",
srcPath: "packages/shared/",
deps: []
},
{
name: "@acme/currency",
srcPath: "packages/currency/",
deps: []
}
];

Task

Implement:

function findPackagesToRegenerate(
packages: Package[],
changedFiles: string[]
): string[]

The function should return the names of all packages that need regeneration.

When Does a Package Need Regeneration?

A package needs regeneration in either of these cases:

1. Its own source file changed

If a .ts or .tsx file inside the package's srcPath changed.

For example:

packages/shared/utils.ts

means @acme/shared needs regeneration.

2. A dependency's source file changed

If a package depends on another package that needs regeneration, it also needs regeneration.

For example:

@acme/ui
↓
@acme/shared

If a file inside @acme/shared changes:

packages/shared/utils.ts

then both packages need regeneration:

@acme/shared
@acme/ui

This should continue through multiple levels of dependencies.

Example 1

Given:

const changedFiles = [
"packages/shared/utils.ts"
];

@acme/shared has a direct change.

The following packages depend on @acme/shared:

@acme/auth
@acme/payments
@acme/ui

So the result should contain:

[
"@acme/shared",
"@acme/auth",
"@acme/payments",
"@acme/ui"
]

@acme/currency should not be included because it is not affected.

Example 2

Given:

const changedFiles = [
"packages/currency/format.ts"
];

Only @acme/currency has a direct change.

@acme/payments depends on @acme/currency, so it is also affected.

Result:

[
"@acme/currency",
"@acme/payments"
]

Important Rules

  • Only .ts and .tsx files should trigger regeneration.
  • Other files such as .js, .json, .md, or .css should be ignored.
  • A package should appear only once in the result.
  • Dependencies can be nested, so you must find all affected packages, not just direct dependencies.
  • Do not modify the input arrays.
  • The order of packages in the input should not matter.
  • Make sure the return array is sorted
Hint

Think of the packages and their dependencies as a graph.

First find the packages with directly changed .ts/.tsx files.

Then find which other packages depend on those packages, and continue until there are no more affected packages.