Bug: Combinatorial explosion in cross-file reference tracing on Prisma generated files

[kazaz-lumida]

Combinatorial explosion in cross-file reference tracing on Prisma generated files

Problem

Domino gets stuck for ~20+ minutes when a PR touches large, highly interconnected Prisma-generated files. The recursive reference-tracing algorithm hits a combinatorial explosion due to the structure of these generated files.

Context

We intentionally commit our Prisma generated files (rather than gitignoring them) specifically so that Domino can trace who imports and uses them. This is the whole point — we want Domino to understand the dependency graph of our generated types. But this means every time a new model is added, Domino has to process the resulting changes to these large, interconnected files.

How to reproduce

Add a new Prisma model (e.g. InventoryFilterGroup) that causes changes to multiple generated files:

File	Lines changed	Total size
InventoryFilterGroup.ts	2,263 (new file)	2,263
User.ts	1,388 lines added	10,346
prismaNamespace.ts	101 lines	3,522
Account.ts	234 lines	4,207

Root cause

For every changed line in every changed file, Domino:

1. Finds the symbol at that line
2. Recursively traces every cross-file reference to that symbol
3. For each reference, finds the container symbol in the importing file, then recursively traces that symbol too

This creates a combinatorial explosion because:

• User.ts (10,346 lines) has 1,388 new lines — all referencing InventoryFilterGroup types. Each of those lines is a changed line that Domino processes, and for each one it finds a symbol and walks the entire import graph recursively.
• prismaNamespace.ts is a barrel/namespace file that re-exports everything. Domino's barrel-file traversal in find_refs_recursive follows export * from '...' wildcard re-exports across the entire generated model tree — 65,985 lines across ~30 files, all cross-referencing each other.

The result is an enormous number of (file, symbol) pairs being visited.

Why this is specific to Prisma models

Other PRs don't touch generated files at this scale. Adding a single new Prisma model causes:

• A new 2,000+ line generated file
• 1,000+ new lines in User.ts (the largest file at 10k lines)
• Updates to prismaNamespace.ts, which is imported by every model file

This creates a reference graph that the recursive algorithm has to fully traverse, and with wildcard re-exports in the barrel files, it visits an enormous number of (file, symbol) pairs.

Suggested mitigations

• Add a depth limit or visited-set deduplication to the recursive reference-tracing algorithm to prevent re-traversing already-visited (file, symbol) pairs
• Allow configuring files/directories to exclude from reference tracing (e.g. Prisma generated output)
• Consider special-casing or short-circuiting barrel files with export * from patterns to avoid expanding the full re-export tree
• Add a timeout or circuit breaker so Domino doesn't block CI for 20+ minutes

Current workaround

Whenever a PR touches these Prisma generated files, we bypass Domino entirely and fall back to nx affected to determine what to build/test. This defeats the purpose of committing the generated files in the first place — we committed them so Domino could understand who uses them, but now we have to skip Domino for exactly the PRs where that tracing matters most.

Environment

• Package: @front-ops/domino
• Generated files: Prisma client output (~30 files, ~65k lines total)

[raye-deng]

Cross-file reference tracing hitting combinatorial explosion on Prisma generated files is a fascinating edge case. The fundamental tension here is that generated code is structurally valid but has connectivity patterns that no human would write — every type references every other type through union types, creating a near-complete dependency graph.

A few observations from dealing with similar problems in cross-file analysis:

1. Generated files need different traversal strategies than authored files. Human-written code has natural modularity boundaries. Generated code (Prisma, GraphQL codegen, OpenAPI types) often produces a single massive interconnected graph. Treating them the same way guarantees blowup.

2. Depth-bounded tracing with heuristic cutoffs. Instead of full recursive traversal, cap the reference depth for files that exceed a connectivity threshold (e.g., if a single file has >50 outgoing type references, switch to sampling). You lose completeness but gain tractability.

3. Semantic grouping over syntactic tracing. For Prisma specifically, the generated types have a predictable structure — each model generates Client, CreateInput, WhereInput, etc. Grouping by model rather than tracing individual type references collapses the graph significantly.

The broader pattern: any cross-file analysis tool needs a "generated code detector" that identifies files with anomalous connectivity and applies different strategies. We ran into the same thing building cross-file consistency checks — Prisma and GraphQL codegen files would cause timeouts until we added heuristics to recognize and handle them differently.

For reference tracing specifically, we've found that checking cross-file inconsistencies (where file A's import of file B's type doesn't match file B's actual export) is more valuable than mapping the full dependency graph. It catches the bugs without needing complete traversal.

[shaharkazaz]

@kazaz-lumida Thanks for reporting the issue, and thank you @raye-deng for sharing insights!
@kazaz-lumida, we made some improvements in handling large files. Can you reproduce the case and test it with the latest version?

[kazaz-lumida]

Sure thing @shaharkazaz , I'll give it a try after the holidays :)