fix(BREAKING CHANGE): dereference caching to prevent infinite loops on circular schemas

[erunion]

We've come across an interesting case with one of our customers OpenAPI definitions where due to the amount of circular references they are using it ends up sending $RefParser.dereference() into an infinite loop that has unfortunately been causing us some pain.

The following is a video of running the dereference.circular=ignore test in this PR without my eventual fix:

uncached.mov

I've killed the process after 20 seconds but we've seen cases where it can run for almost an hour trying to dereference this circular API definition. In investigating this we've identified a couple issues:

1. When dereferencing this specific schema the event loop gets blocked in the process preventing the options.timeoutMs check and exception from ever getting hit.
   • We were able to resolve this by adding a supplementary timeout check when the dereference crawler processes each property within an object.
2. The dereference cache isn't being fully taken advantage of.

In investigating the cache issues we noticed a couple more issues:

Core issues with Set caches

The Set objects that are used for parents and processedObjects don't appear to be fully utilized because these are often setting objects, and Set does not do object deuping:

const set = new Set();
set.add({ type: 'string' });
set.add({ type: 'string' });

console.log({ set: Array.from(set), has: set.has({ type: 'string'} )})

> {set: Array(2), has: false}

I'm not convinced that any of the .has() checks being executed on these stores are currently working and I made an attempt at pulling in flatted¹ to create consistent and unique keys off of these values however a couple unit tests broken in unexpected ways and ended up moving on. I would love to spend some more time investigating this because I think in extreme cases like ours we could really improve memory usage during dereferencing.

The dereference cache is only being used for non-circular objects

After crawling to dereferencing an object and either updating the original schema or resetting it to the original $ref if dereference.circular=ignore is set that resulting object is saved into the dereferenced cache Map. This map is referenced at the beginning of the dereference$Ref function however the cache is only utilized if the found object is not circular.

I was unable to uncover a reason why this was the case but without this cache being utilized this dereferencer would continuously, even despite dereference.circular=ignore being configured, crawl and re-dereference objects it had already seen. Changing this logic to always return the cache if we found something brought dereferencing our use case down from ∞ to less than a second.

cached.mov

_{Ignore the logs in this video, it was recorded while I was still working on this fix.}

BREAKING CHANGE: dereference caching to prevent infinite loops on circular schemas

Footnotes

1. Because JSON.stringify() cannot serialize circular objects. ↩

[erunion]

The snapshot changes in this look odd but because we are now always using the cache for circular schemas, and because a -> b -> a means that a -> a, these dereferenced $ref pointers are now a because they were stored and retrieved from the cache as such.

[coveralls]

Pull Request Test Coverage Report for Build 14412904745

Details

• 16 of 16 (100.0%) changed or added relevant lines in 1 file are covered.
• No unchanged relevant lines lost coverage.
• Overall coverage increased (+0.3%) to 92.926%

---

Totals
Change from base Build 13576959097:	0.3%
Covered Lines:	1644
Relevant Lines:	1744

---

💛 - Coveralls

[jonluca]

This is great! This is actually a bug I've been thinking about for a while. In general I think the cacheing mechanism needs to be fully rewritten, it's confusing and written improperly. Maybe I'll get Claude to take a stab at it in a while.

This PR looks good.

Unfortunately the change in how we process / return circular references makes me think that this is a breaking change. I think we need to label this as a BREAKING CHANGE pull request and do a major version bump, just in case.

[jonluca]

re: using unique keys for the Set cache, we could define something like hashKey from @tanstack/react-query

import { hashKey } from "@tanstack/react-query";

it's a somewhat heavy operation (at least way heavier than a native object hash in javascript), but it would lead to stable keys. I'm not sure what it does wrt circular references though.

[erunion]

Unfortunately the change in how we process / return circular references makes me think that this is a breaking change. I think we need to label this as a BREAKING CHANGE pull request and do a major version bump, just in case.

Agreed that this definitely feels like a breaking change. I'll update the PR title.

[github-actions]

🎉 This PR is included in version 12.0.0 🎉

The release is available on:

• npm package (@latest dist-tag)
• GitHub release

Your semantic-release bot 📦🚀

[erunion]

Thanks so much @jonluca, you're amazing.