Comments (7)
We were discussing this on Discord, but adding here for visibility: I think it could be a good idea to build an initial version without dependency graph and use it to power the GraphQL analyzer. Might be a good PoC for a first iteration.
from biome.
Another word of advice:
salsa
isn't a library; it is a framework, which means our code architecture may have to change to accommodate it. Some months ago, I also tried for fun to include the oldsalsa
, and I am certain that things will have to change, however we can incrementally add stuff to the database.
I think salsa
is a pretty impressive architecture, but I am indeed slightly wary of the amount of changes it would require for it to fit into Biome's architecture.
Another thing to consider: As our plugin efforts progress, we may want to give plugins the ability to extract information from files similar to how Rust services can. This might be possible with salsa
too, but I'm not sure if it will become harder to achieve.
We could use on-demand traversal for these cases. I think we could even give up on this, because if the user is explicitly asked to (globally) ignore a file or directory, this is surely for a good reason. The user might be confused by getting parsing errors for an ignored file.
(emphasis mine)
This sounds dangerous. I think ignore instructions from the user should be respected as far as analysis is concerned, but not necessarily as far as extraction/discovery is concerned. Example: node_modules
is usually ignored, but you'd still want to extract type information from it.
Note that we need to clarify one thing: if a user globally includes directories, we should only process them. However, if a user doesn't use include and only uses ignore, then technically we could process files outside the traversed hierarchy. Is that what we want?
I think indeed processing files outside the traversed hierarchy is what we want, and may even need to extract information from dependencies. I would say this is true even if the user only specified a limited set of includes
. In my suggestion, this is effectively what Phase 1b is about, and which indeed would have the ability to traverse outside files/directories from the initial traversal.
It is not clear to me why a module graph is needed for multi-file analysis.
We just need a way to resolve imported files and a way to extract data for those files.
Of course, the module dependency graph will be really useful for import analysis (cycle detection, ...).
I think it's more a convenience than a necessity. Indeed as soon as you extract imports and are able to resolve them, you already have the graph implicitly. Putting it in a data structure makes access more convenient. Cycle detection is indeed a good example of that :)
I wouldn't say it necessarily needs to be a petgraph
, btw. As long as we track files in our workspace, a simple list of paths (after resolving) of which other workspace files it depends on might also be enough.
If we keep our linter query-based system, most of the current linter rules could be executed in the first phase because they visit the AST. Is there any reason to defer them until after the dependencies have been resolved?
You're right, they could be. The main reason I figured it might be better to do all analysis in phase 2 was simplicity: If all analysis rules run in the same phase, there might be less bookkeeping involved.
Maybe your suggestion could actually improve performance by giving the workers more to do while we also perform a lot of filesystem I/O, so I wouldn't rule out that option either.
from biome.
Thanks for this outline!
In general I agree with the two-pass approach. I think indeed there should be one pass that collects data we need and one that does analysis with the data available over all files. As you mentioned, between the passes there may indeed be a step that detects and defines dependencies as well; the creation of the Project data structure.
I saw one part that made me cautious:
- try to compute data only when requested;
- don't overdo it, try to compute only the data requested;
- think about queries, where a consumer asks for data, and the provider delivers them (and ideally caches them);
I am somewhat afraid this might be approaching the direction from the wrong angle. Rather than querying from the place where the data is needed and caching results, I think itโs better to build (most of) the data from the ground during the first phase so that itโs already available when the second phase starts. This does mean we end up computing some information we end up not querying, but I see some convincing reasons we may want to take this approach anyway:
- It is much easier to parallelize the work. Workers during phase one will be able to do this per file without complex synchronization overhead. Workers during phase two have it available to them without needing to wait for one another.
- Because it requires less synchronization it will also be easier for us to build and have fewer bugs.
- I think this approach also better align with the direction we want to take for type inference, meaning we may reuse some of the infrastructure.
And finally, if the goal is to avoid doing unnecessary work, I think itโs best to split the types of data we gather into various services, and only activate the services that have one or more rules registered for them. But if we make data gathering itself too fine-grained, I think weโll make things too complex for ourselves and Iโm skeptical the work we safe would outweigh the benefits of better parallelization.
Unrelated question: Since the data structure is called Project for now? Do you think this provides a good opportunity to improve our monorepo support as well?
from biome.
So I think a little bit more concretely I would suggest something in the following direction:
Initialization step: Config Resolution
This is very much like today, we load the config files. Since we decide here which rules should be enabled, weโll know which services to activate for the next step.
Phase 1: Traversal and Discovery
This step performs the filesystem traversal and parses all the supported files. It also extracts file-specific data for enabled services.
Examples of services could be:
- Extract project structure (
package.json
,deno.json
) - Extract list of imported files/packages this file depends on (these would still be unresolved at this point)
- Extract type information
- Extract installed dependencies (
package.json
,deno.json
) - Extract import maps (
tsconfig.json
,deno.json
) - Extract GraphQL snippets
I included project structure in this list because I think if we do this right, it might help us to fix our monorepo support. This probably means weโll treat package.json
as a JSON file in the project like any other, but weโll have a service that recognizes it as a project root, extracts its dependencies, etc.. It wonโt care yet if itโs a nested project, since thatโll be up to the next step to resolve.
Intermediary step: Project Resolution
At this point we look at everything weโve gathered and build a dependency tree. We create a one or more Project
s a and define the relations between them.
This step is probably hard to parallelize, since graph manipulation is difficult to multi thread, which is why I think we should have most data available already.
File resolution also happens here, and I think we can be clever here by not doing any additional filesystem I/O. Weโve already done a traversal, so we know the file paths and their contents.
Phase 1b: Traversal and Discovery of Dependencies
Some services, such as type inference, may want to extract information from external packages. We couldnโt do that during phase 1, since we hadnโt done any file resolution yet. But now that we know and have identified what is missing we can repeat phase 1 for these resources. The main difference is that it wonโt be a file system traversal, but traversal of the dependency graph for missing data. It may take file system access, or even network access, to fully resolve everything though.
Phase 2: Analysis
Now we have well-defined projects, their dependencies, full file resolutions and a bunch of extracted metadata. Itโs time to run our rules :)
This can be fully parallelized again since the data in the services is fixed at this point.
from biome.
One more thing Iโd like to add is that I think an approach like this could scale very well to our LSP use case too, since every time a file is changed, we just re-run the phase 1 discovery on it after which we only may need to update the Project
data structure(s) to get back into a fully consistent, up-to-date state again.
from biome.
There's also one more thing that I would like to consider as part of this refactor/feature. salsa
.
If you don't know salsa
, it is an on-demand computation and memoisation framework.
I have been looking at salsa
for a looooong time, and we've had plans to try to introduce it inside Biome. Ruff is also evaluating it. There's a big question mark, though: at the moment, they are rewriting it, and they will land the 3.0 version. However, the developments are very slow, and we currently don't know when they will finish it. However, I know that Micha from Ruff is currently helping with the developments, the team had a meeting about shipping v3 and more. So I am hopeful.
Their website lists the documentation of the upcoming v3, and the old website is now gone.
Another word of advice: salsa
isn't a library; it is a framework, which means our code architecture may have to change to accommodate it. Some months ago, I also tried for fun to include the old salsa
, and I am certain that things will have to change, however we can incrementally add stuff to the database.
The documentation lacks a bit, especially when it comes to how to use salsa
inside a query compiler or IDE. However, I know that they plan to expand the docs in that territory.
from biome.
From a CLI perspective, a way to build a Project and its graph is by doing two passes of the file system.
One pass to collect all files. A second pass to check the files.
The second pass is more challenging because, between the first pass and the second pass, we don't have an entity that will tell the WorkspaceServer which files should be checked.
One thing I am afraid of is unnecessary traversing of directories (including symbolic links).
In the past we had some performance issues with that.
We could take a more granular approach, where we load the files in the currently traversed directory and decide - based on .gitignore
, and global ignore
/include
- which subdirectories to traverse.
This has one drawback: a handled file may import a file in an ignored
directory. However, even by traversing all the file hierarchy, we still have this problem because a handled file can import an unhandled file outside the traversed hierarchy.
We could use on-demand traversal for these cases. I think we could even give up on this, because if the user is explicitly asked to (globally) ignore a file or directory, this is surely for a good reason. The user might be confused by getting parsing errors for an ignored file.
Note that we need to clarify one thing: if a user globally includes directories, we should only process them. However, if a user doesn't use include
and only uses ignore
, then technically we could process files outside the traversed hierarchy. Is that what we want?
Using this approach, will require to slightly precise or change the semantic of our ignore
/include
:
- Global
ignore
/include
and.gitignore
control which directories we traverse and which
files we process (parse, extract ypes, dependency graph). - linter/formatter
ignore
/include
don't prevent traversing of a directory or
processing (parsing, type extarction, ...) of a file.
It only prevents linter/formatter execution. - Paths listed as CLI arguments could be similar to linter/formatter
ignore
/include
.
However, I am unsure where the traversal of the file hierrachy should start if
we apply a such semantic. Maybe the current directory where the command is executed?
Or the directory where the biome config file appears (This could be a bad idea if a project has no config file)?
Fortunately, a module graph can be built with petgraph, which implements these traits.
It is not clear to me why a module graph is needed for multi-file analysis.
We just need a way to resolve imported files and a way to extract data for those files.
Of course, the module dependency graph will be really useful for import analysis (cycle detection, ...).
Phase 1: Traversal and Discovery
Phase 2: Analysis
If we keep our linter query-based system, most of the current linter rules could be executed in the first phase because they visit the AST. Is there any reason to defer them until after the dependencies have been resolved?
The main difference is that it wonโt be a file system traversal, but traversal of the dependency graph for missing data. It may take file system access, or even network access, to fully resolve everything though.
from biome.
Related Issues (20)
- ๐ Improve functionality of import type HOT 1
- ๐ Improve functionality of CLI --only and --skip HOT 1
- ๐ lint-staged + .d.ts file HOT 6
- ๐ Remove undocumented values for CLI options
- ๐ Make install script that keeps biome.json $schema version in sync with package version HOT 1
- @biomejs/js-api
- Saving a file in VSCode doesn't reformat a line with a comment on a JSX property that that's too long, but `biome format --write` does HOT 1
- ๐ emoji not supported in CSS parser HOT 1
- biome check --stdin-file-path=file.ts doesn't return stdout HOT 3
- ๐ useFilenamingConvention ignores style in extension
- ๐ Implement `noEnum` HOT 2
- Ignored files are not ignored when using --staged or explicitly specified in CLI HOT 4
- ๐a11y/useAltText: {...props} causes false positive
- ๐ The --only option is ignored when using the --unsafe option HOT 1
- ๐ lint/suspicious/noRedeclare: false positive on functions declared in switch blocks HOT 1
- ๐ noUnusedImports supports custom jsxFactory HOT 1
- ๐ `useExhaustiveDependencies` incorrectly evaluates property access of non-null operator asserted object
- ๐ `noAriaHiddenOnFocusable` doesn't handle a bracketed number for `tabIndex`
- ๐ Imports exceed lineWidth limit HOT 2
- ๐ Missing codegen check in CI
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. ๐๐๐
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google โค๏ธ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from biome.