perf(hmr): skip traversed modules when checking circular imports

[skovhus]

Description

This PR is fixing graph traversal issue where long module graph seems to be explored repetitively, at least the HMR reloading is super slow and can sometimes result in the server becoming irresponsive. It is likely related to the codebase having a lot of barrel files and circular imports.

Additional context

I just tried 5.0 out an a large codebase with a lot of circular imports and barrel files. Unfortunately we often end up on cases where Vite becomes irresponsive when changing certain files.

The regression is related to #14867.

I could come up with a test case that reproduces this. @ArnaudBarre do you have an idea on how to do that?

The solution was suggested by @ArnaudBarre here.

Performance improvement: most importantly the server is now responsive again, but for some files that took 14 seconds to determine a circular import (vite 5.0.0), it now takes ~10 ms.

What is the purpose of this pull request?

• Bug fix
• New Feature
• Documentation update
• Other

Before submitting the PR, please make sure you do the following

• Read the Contributing Guidelines, especially the Pull Request Guidelines.
• Check that there isn't already a PR that solves the problem the same way to avoid creating a duplicate.
• Provide a description in this PR that addresses what the PR is solving, or reference the issue that it solves (e.g. fixes #123).
• Update the corresponding documentation if needed.
• Ideally, include relevant tests that fail without this PR but pass with it.

[ArnaudBarre]

I spent sometimes looking at the code yesterday and I don't see how it could end up in infinite recursion. My only thought was just that it was slow to explore the graph, but even with if a big graph it should not freeze your computer, just make HMR really slow. So there is probably something I missing, but if this change works and the test are passing I think this is still a good change. Maybe @bluwy will understand better what is happening.

[ArnaudBarre]

Thanks for testing it and making the PR!
Edit: You forgot the line to pass the set in recursion

[skovhus]

I spent sometimes looking at the code yesterday and I don't see how it could end up in infinite recursion. My only thought was just that it was slow to explore the graph, but even with if a big graph it should not freeze your computer, just make HMR really slow. So there is probably something I missing, but if this change works and the test are passing I think this is still a good change.

Yeah I also tried to think what could go wrong. Also tried to make a set of the traversed chains urls and checked if the current chain was in there without luck. After introducing traversedModules I also tried not returning in case node was included, but then we run out of memory (which signals that we are in an infinite graph traversal).

Edit: You forgot the line to pass the set in recursion

Fixed. :)

[bluwy]

I can't really think of a case where a recursion could happen too, but I can see traversedModule being a nice perf improvement. For cases like:

graph TD
    A ---> B
    A ---> C
    B ---> D
    C ---> D
    D ---> E

If D already failed once, we can early out and not process it anymore (since we also do a depth-first search). Perhaps the lack of this was causing a huge memory pressure and not necessarily a recursion 🤔

[skovhus]

I can't really think of a case where a recursion could happen too, but I can see traversedModule being a nice perf improvement.

I just verified the performance improvement. Before isNodeWithinCircularImports took 14 seconds to determine a circular import on one of our files, after this PR it takes 10 ms. So a nice ~1400X speed up. :)

[bluwy]

Thanks!