asyncapi / asyncapi/parser-js

Parser repeatedly traverses shared schema graphs during circular-reference resolution

Open
#1,230 1 comment 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.