Linting circular import dependencies

[Christer Eliasi-Swahn]

I was trying to create an analyzer plugin to create a lint rule for circular import dependencies.

This turned out to be quite tricky, since a plugin's normal node visitor pattern is to be called for each node (to determine a possible warning/message for it), but this kind of rule depends on the whole package state, and a change to another file can affect the result for the currently visited file.

It's not difficult or slow to find import cycles within a package when run once - but it's not performant to run the same search from scratch for every import node visited. So I investigated caching the search and looking it up for each import node visited instead. But this is not straight-forward, especially cache invalidation becomes hard (upon an import statement being modified or deleted).

I couldn't find answers to the following in the docs, can someone assist?

A. Analyzer processing lifecycle

When are the nodes of a given compilation unit actually revisited? When reprocessing a compilation unit, is it known what has changed, or do I need to determine the delta myself? Is it possible to plug in to this "compilation unit revisit" directly instead of on the individual AST nodes?

B. Internal cycle awareness

The analyzer by nature of resolving the Dart language already has an idea of the referential cycles in the source code, explicitly or implicitly. Is this information more explicitly available to a plugin, in which case identifying circular dependencies might be straight-forward?

Cheers,

/ Christer

[Brian Wilkerson]

When are the nodes of a given compilation unit actually revisited?

Whenever the result of analyzing the file might have changed. It isn't possible to know whether the results have actually changed until the analysis has been performed.

When reprocessing a compilation unit, is it known what has changed, or do I need to determine the delta myself?

Analysis rules are run as part of analyzing a file, so they're run while figuring out what has changed. In fact, any change in the diagnostics reported by an analysis rule is considered to be a change to the analysis results, so no, it isn't possible to know what has changed at the time the analysis rule is run. I don't think you can determine the delta either. The analyzer is designed to reanalyze each library from scratch and doesn't have any notion of a delta.

Is it possible to plug in to this "compilation unit revisit" directly instead of on the individual AST nodes?

The revisit is done in terms of the AST nodes, so analysis rules are already as directly connected as they can be.

The analyzer by nature of resolving the Dart language already has an idea of the referential cycles in the source code, explicitly or implicitly. Is this information more explicitly available to a plugin, in which case identifying circular dependencies might be straight-forward?

Yes, it does, but no, that information isn't available via the public APIs. If you'd like to do so you can open an issue (https://github.com/dart-lang/sdk/issues/new/choose) to request a public API for this information.

In the absence of an actual API, I would have expected that it would be relatively straightforward to walk the element model (`LibraryElement`) to find all of the import and export information and determine whether the current library is reachable from any given import / export. I'm a little surprised that it's not efficient enough. Perhaps you can describe the algorithm you're using.

--
You received this message because you are subscribed to the Google Groups "Dart Analyzer Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to analyzer-discu...@dartlang.org.
To view this discussion visit https://groups.google.com/a/dartlang.org/d/msgid/analyzer-discuss/9a305ece-38b5-4f00-82a7-6a3a9faf916bn%40dartlang.org.

[Christer Eliasi-Swahn]

Thanks for the reply!

> In the absence of an actual API, I would have expected that it would be relatively straightforward to walk the element model (`LibraryElement`) to find all of the import and export information and determine whether the current library is reachable from any given import / export. I'm a little surprised that it's not efficient enough. Perhaps you can describe the algorithm you're using.

A straight-forward non-caching DFS implementation of this (that avoids inspecting the same subtree twice) takes about 1-3 seconds to re-run when working in VSCode, for a package with 74 source files, and each file having on average maybe 5 imports from within the same package (it only looks at package-internal imports) - that's about 300 import statements to run the cycle search for.

Regards

/ Christer

[dark...@gmail.com]

You should be able to use caching.

Using an Expando using the LibraryElement as key should enable avoiding duplicate work.