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:
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
Description
resolveCircularRefsusesvisitedas 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:
Passing a document whose
json()method returns this graph toresolveCircularRefsreads the leaf 4096 times on currentmaster; 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
$refthat 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/parser3.6.3masterataded935e6a5e2d420acb9ae4a6b5532cc30bbf45