Interface type explosion causes error on query

[martin-svanberg-northvolt]

Describe the bug
Attempting to query an interface with many implementations results in an error.

To Reproduce

We have an interface (FactoryUnit) with more than 70 implementations. It's defined as follows:

interface FactoryUnit {
  id: ID!
  # ...
  unitState: FactoryUnitState
}

type FactoryUnitState {
  id: ID!
  # ...
}

We try to run the following query, which gives an error:

Query:

query {
	identity(id: "...") {
		id
		... on FactoryUnit { unitState { id } }
	}
}

Expected behavior
It should not return an error when querying.

Output

{
	"errors": [
		{
			"message": "value retrieval failed: router bridge error: the deno runtime raised an error: `request: couldn't receive response couldn't deserialize payload `6476623271848066925`: `deno: couldn't deserialize response : `Error(\"invalid neither null nor empty object: found Object {\\\"code\\\": String(\\\"QUERY_PLANNING_FAILED\\\"), \\\"exception\\\": Object {\\\"stacktrace\\\": Array [String(\\\"RangeError: Invalid array length\\\")]}}\", line: 0, column: 0)``.`",
			"extensions": {
				"code": "INTERNAL_SERVER_ERROR"
			}
		}
	]
}

Desktop (please complete the following information):
macOS Monterey, but issue also visible on the server running Alpine Linux 3.16

Additional context
We've traced this issue to the following function in Apollo Federation, which appears to be a function with exponential time and space complexity:

federation/query-graphs-js/src/graphPath.ts

Line 2167 in 92a9dff

function flatCartesianProduct<V>(arr:V[][][]): V[][] {

It fails when trying to construct an array of length 2^70. Given the comment above flatCartesianProduct, it seems that this is a known issue.

[abernix]

Thanks for opening this. I'm moving this to the federation repository since anything that can be fixed will be in the federation repository, rather than in the Router itself.

[abernix]

As questions which could be worth understanding that I don't see provided:

1. Are you using Federation 2.x to compose this supergraph? Or is this a Federation 0.x supergraph that you're running with Federation 2 runtimes?
2. Are there any of your subgraphs which haven't been updated to Federation 2.x yet? (e.g., don't have @link directives in their SDL)?
3. Can you provide a reproduction of this with a contrived set of subgraphs and interfaces & types?

[martin-svanberg-northvolt]

1. This is using Federation 2.3
2. I've verified that all of them are on either 2.0 or 2.3
3. Sure! Give me some time and I'll try to set up a minimal reproduction