Parser repeatedly traverses shared schema graphs during circular-reference resolution
- Dominant language
- TypeScript
- Stars
- 144
- Forks
- 144
- Avg merge
- 6m
- Merged PRs (30d)
- 11
Description
### Description
`resolveCircularRefs` uses `visited` as a recursion-stack guard and deletes each object after returning from it. This prevents recursion loops, but it also means that a dereferenced object shared by many parents is traversed again for every path. A diamond-shaped schema graph therefore grows exponentially during this custom operation even though the in-memory graph itself is small.
In a real-world AsyncAPI 3 document with heavily reused envelope schemas, validation completed in a few seconds but parsing/generation remained CPU-bound for more than 10 minutes and used roughly 700 MB of memory. A CPU profile attributed about 73% of samples to recursive calls in `resolve-circular-refs.ts`.
### Minimal reproduction
Create one leaf object with an enumerable getter, then wrap the same object twice at each of 12 levels:
```js
let visits = 0;
const leaf = {};
Object.defineProperty(leaf, 'value', {
enumerable: true,
get() {
visits += 1;
return 'value';
},
});
let graph = leaf;
for (let level = 0; level < 12; level += 1) {
graph = { left: graph, right: graph };
}
```
Passing a document whose `json()` method returns this graph to `resolveCircularRefs` reads the leaf 4096 times on current `master`; it only needs to be processed once.
### Expected behavior
The traversal should retain its active recursion-stack guard, while separately memoizing objects only after their complete subtree has been processed. Objects containing a `$ref` that cannot yet be resolved for the current inventory path must not be marked complete, because a later path may provide the required resolution context.
### Version
- `@asyncapi/parser` 3.6.3
- current `master` at `aded935e6a5e2d420acb9ae4a6b5532cc30bbf45`
Contributor guide
Research direction
Start with resolve-circular-refs.ts and the resolveCircularRefs entry point, then run the minimal shared-schema reproduction to observe repeated getter visits. Done means retaining the active recursion-stack guard while processing completed subtrees only once, without memoizing objects whose $ref still needs a later inventory path.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- typescript
- Domain
- performance, tooling
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 58/100