RFC: Linter

[Boshen]

In this discussion I will document how the linter is going to be implemented.

Prioritizations are performance, simplicity and contribution friendly.
This is an initial draft for the first MVP, which may lack some features, such as module resolution.

I'll use structured comments below for better discussion.

[Boshen]

File Traversal

I will use the ignore crate for file traversal. .eslintignore files can be added by calling add_custom_ignore_filename.

[charliermarsh]

We use the ignore crate. It works well. But we only use it for .gitignore support, and not for enforcing Ruff's custom inclusion and exclusions, the primary reason being that we support ESLint-like hierarchical configuration, so the set of exclusions can actually change as you traverse the hierarchy and parse configuration files.

[Brooooooklyn]

https://github.com/napi-rs/node-rs/blob/main/packages/deno-lint/src/lib.rs#L137

[charliermarsh]

Oh interesting, and it resolves those hierarchically? Ruff can't use that AFAICT since the exclusions are defined in pyproject.toml files (and pyproject.toml files can extend other pyproject.toml files) rather than in a flat gitignore-like file (a convention picked up from other tools in the ecosystem), but it definitely looks preferable to having to resolve those manually if it works.

[strager]

Does ignore support placing file watches? File watches are useful for a watch/server mode. File watching needs to be integrated with tree traversal to be done correctly; if you find all the files then add watches, you open yourself up to race conditions.

[Boshen]

ignore doesn't do file watches. For this scenario I will integrate oxc into lsp extensions in text editors, which means I won't be using walkdir / ignore for file traversal, and the gitignore / eslintignore logic will be handled and cached differently.

[Boshen]

Traversal

The goal here is to maximize multi-core parallelization, where we want to traverse each file, each lint rule and each AST node by using par_iter from the rayon crate.

The algorithm:

• for each file (par_iter)
  • parse into AST
  • for this AST
    • do a visiting pass, for this pass
      • build a parent pointing tree using the indextree crate, the nodes of this tree is untyped [0].
      • for semantic analysis, build its scope tree, symbols table and control flow graph
  • for each lint rule (par_iter)
    • for each node of indextree (par_iter)
      • call LintRule.run
• collect all diagnostics and emit them

[0] The untyped node is this gigantic enum

https://github.com/Boshen/oxc/blob/c8cc809766945e7e791a9d7a305bd0cd774f842d/crates/oxc_ast/src/ast_kind.rs#L5-L12

[Boshen]

do you plan to have lint rules that work "multi-files"?

Let's move this to another #38 (comment)

[charliermarsh]

We don't do a separate visiting vs. linting pass, but it seems like a nice idea. I'm not a big fan of our current approach to this, it still uses the approach I wrote initially which does a single combined pass that simultaneously builds up the scope tree and calls out to lint rules at the appropriate time. Is the downside of the approach you described above not that you need to store the semantic scope analysis for every node, so that you know what bindings were defined when you go to run the lint rule?

We do use something like indextree but it's just manually implemented. The AST outlives the AST checker, so the checker just inserts nodes into an array and stores (e.g.) stacks of parent references as it goes. I don't know if it's the "right" approach but it does mean we do very few allocations in the AST pass (mostly just for bindings and lint violations).

[Boshen]

Is the downside of the approach you described above not that you need to store the semantic scope analysis for every node, so that you know what bindings were defined when you go to run the lint rule?

I don't know if it's the "right" approach but it does mean we do very few allocations in the AST pass (mostly just for bindings and lint violations).

Basically I'm following the eslint / clippy approach, where the linting phase is standalone, and every rule has its logic tucked into a single file, all semantics are built prior and fed into the rule.

I do like your approach though, it's inspiring because I faced the issue of having to allocate huge scope trees and symbol tables, which slowed down things a bit. Maybe I can find a middle ground for this.

[charliermarsh]

The downside to Ruff's approach is that the rules and the binding / semantic logic are all tightly coupled. checkers/ast.rs is now an enormous file that both handles all the binding tracking and calls out to rules at the appropriate moment in time. It's hard to break up (though we'll have to do it at some point) and hard to parallelize. So, I wouldn't necessarily recommend it, although it has "worked" for us thus far :)

[jfmengels]

@charliermarsh I've been thinking about this recently, and another downside with your approach (but tell me if I'm wrong, I'd love to know a solution to this problem!) seems to me that rules can't look ahead in the AST. Something that happens in elm-review sometimes (not super often but still) is that for convenience's sake, the rule would like to know like the name of every top-level declared type/function, and the traverse the file with that information in mind. Without this look-ahead, rules would have to hold to some potential data while waiting to know whether something was declared or not, and then at the end report errors or discard the data.

An example of that could be if you want a rule that reports references to non-existing functions (given everything being hoisted, which is at least the case in Elm). If you can do a look-ahead to see which functions are available, then as soon as you find an unknown name, you can report it. If you don't, you need to collect all the references and their location, while collecting the declared names, and at the end report the problems.

So I'm thinking that if you don't do look-aheads, then some rules will be more annoying to write but also potentially be more expensive in memory and/or CPU. That said, it looks like with your approach you could still do look-aheads, but not with the semantic analysis helpers figured out.

[Boshen]

Lint Rule

A Lint rule implements the following trait.

pub trait Rule: Default {
    const CATEGORY: RuleCategory;

    fn run_once(&self, _ctx: &Semantic) -> Vec<Diagnostic> {
        vec![]
    }

    fn run<'a>(&self, _node: &AstNode<'a>, _ctx: &Semantic<'a>) -> Vec<Diagnostic> {
        vec![]
    }
}

These two methods returns a Vec because they can return multiple diagnostics.

Semantic

The semantic struct wraps everything associated with the AST being called upon. For example scopes, symbols, cfg, trivias etc.

There are lint rules which will only act upon semantic data, so I added a run_once method for convenience.

AstNode

AstNode wraps all the context for this node

pub type AstNode<'a> = indextree::Node<SemanticNode<'a>>;

pub struct SemanticNode<'a> {
    pub kind: AstKind<'a>,

    pub flags: NodeFlags,

    /// Associated scope
    pub scope_id: ScopeId,

    /// Associated control flow node
    pub flow_id: Option<FlowNodeId>,
}

bitflags! {
    #[derive(Default)]
    pub struct NodeFlags: u8 {
        const Class             = 1 << 0; // If Node is inside a class
        const HasImplicitReturn = 1 << 1; // If function implicitly returns on one of codepaths (initialized by binding)
        const HasExplicitReturn = 1 << 2; // If `AstKind::FunctionBody` has explicit reachable return on one of codepaths
        const HasBreak          = 1 << 3; // if `AstKind::WhileStatement` or `AstKind::DoWhileStatement` or `AstKind::ForStatement` has reachable break statement in body.
        const HasYield          = 1 << 4; // if Function has yield statement in body.
        const HasAwait          = 1 << 5; // if Function has await statement in body.
        const Export            = 1 << 6; // Export Declaration
    }
}

[jfmengels]

If a rule wants to collect information when going from one node to another, how would they do that? Store the data in some global variable?

Example: I want to report calls to Module.function(), but only if Module corresponds to the import of a specific module (like `import * as Module from "./module")

[strager]

If a rule wants to collect information when going from one node to another, how would they do that? Store the data in some global variable?

You can store state in fields in the struct implementing the Rule trait.

[jfmengels]

And those would then be relative to the file to be analyzed? The framework would then have to create a new Rule for every file, in order not to reset that data. Right?

[strager]

The framework would then have to create a new Rule for every file, in order not to reset that data. Right?

Good question. I don't know what @Boshen had in mind.

[Boshen]

I've implemented 140 rules internally and I had the exact question after writing 30 rules or so. I was also frustrated and started implementing mutations just like how ESLint is doing. Then I started thinking about the problem domain - ESLint had to do this because it doesn't have access to anything else, but I'm writing a compiler, I have everything! It then hit me: I should just make the semantic analyzer better, all semantic context should be efficient reads, mutations block performance, and rules will need to redo works sometimes, which is what I've been seeing in ESLint.

So in the end I had a slightly more complicated semantic analyzer, but super clean lint rules.

[Boshen]

Authoring Rules

Writing rules looks almost identical to ESLint, except its Rust 😄

use diagnostics::Diagnostic;
use ast::AstKind;

use crate::{AstNode, Rule, RuleCategory, Semantic};

/// https://eslint.org/docs/rules/no-debugger
#[derive(Debug, Default)]
pub struct NoDebugger;

impl Rule for NoDebugger {
    const CATEGORY: RuleCategory = RuleCategory::Correctness;

    fn run<'a>(&self, node: &AstNode<'a>, _: &Semantic<'a>) -> Vec<Diagnostic> {
        let AstKind::DebuggerStatement(stmt) = node.get().kind else { return vec![] };
        vec![Diagnostic::NoDebugger(stmt.node.range())]
    }
}

#[test]
fn test() {
    use crate::rules::LintRule;
    use crate::test_util::test;
    let pass = ["var test = { debugger: 1 }; test.debugger;"];

    let fail = ["if (foo) debugger"];

    test(LintRule::NoDebugger(NoDebugger), &pass, &fail);
}

Tests are written inside the same file for convenience.

[charliermarsh]

One thing I'm happy about with Ruff is that we have a common define_violation! macro that also picks up the rustdoc -- this is inspired by Clippy though the implementation is a little different:

define_violation!(
    /// ## What it does
    /// Checks for `__init__` methods that are turned into generators by the
    /// inclusion of `yield` or `yield from` expressions.
    ///
    /// ## Why is this bad?
    /// The `__init__` method is the constructor for a given Python class,
    /// responsible for initializing, rather than creating, new objects.
    ///
    /// The `__init__` method has to return `None`. By including a `yield` or
    /// `yield from` expression in an `__init__`, the method will return a
    /// generator object when called at runtime, resulting in a runtime error.
    ///
    /// ## Example
    /// ```python
    /// class InitIsGenerator:
    ///     def __init__(self, i):
    ///         yield i
    /// ```
    ///
    /// ## References
    /// * [CodeQL: `py-init-method-is-generator`](https://codeql.github.com/codeql-query-help/python/py-init-method-is-generator/)
    pub struct YieldInInit;
);

[Boshen]

Rule Configuration

Configurations are parsed from json into normal structs. They can accessed from the rule.

/// https://eslint.org/docs/latest/rules/no-extra-boolean-cast
#[derive(Debug)]
pub struct NoExtraBooleanCast {
    enforce_for_logical_operands: bool,
}

impl Default for NoExtraBooleanCast {
    fn default() -> Self {
        Self { enforce_for_logical_operands: true }
    }
}

impl Rule for NoExtraBooleanCast {
    fn from_json(value: serde_json::Value) -> Self {
        Self {
            enforce_for_logical_operands: value
                .get(0)
                .and_then(|v| v.get("enforceForLogicalOperands"))
                .and_then(|v| v.as_bool())
                .unwrap_or_default(),
        }
    }
}

[ematipico]

One thing that I didn't like while writing the configuration for Rome's lint rules, was the fact that rules with options needed to be parsed at a later time, and as a consequence the configuration had to be parsed multiple times:

For example, given this meta-configuration:

{
	"linter": {
		"category1": { "noDebugger": { "options": {}  }, "noConsole": { "options": {} }  },
	}
}

It would mean that "options": {} blocks need to be saved as a RawValue and then parsed later when calling the rule. From my point of view, I think it's better to parse the options before.

[Boshen]

I also had trouble dealing with json schemas from eslint's configuration operations, some of them are super dynamic, which can't be parsed statically from serde, so I had to come up with the from_json method and manually parse them. But I think the code here is a bit cleaner than eslint because its isolated away, where as in eslint its part of the create method:

https://github.com/eslint/eslint/blob/f9f195ef12deb114fb86763010a23ea0cb4c78d1/lib/rules/no-magic-numbers.js#L83-L90

[Boshen]

was the fact that rules with options needed to be parsed at a later time, and as a consequence the configuration had to be parsed multiple times

I didn't know about this. For my approach, the rules are just structs, so they will only be constructed once and then passed to the lint runner.

[ematipico]

The issue I have is that if there's an issue in the JSON (syntax error or invalid values), you'd only know that only when you actually attempt to run the rule, which is a bit annoying.

[Boshen]

ESLint Configuration Comments

For eslint-disable and eslint-disable-next-line configuration options, I will use the parser to parse them into a structured data, possibly a BTreeMap, something like

struct Trivias {
  eslint_configuration_comments: BTreeMap<u32, (Rule, Span)>, // keyed by span.start
}

The BTreeMap::range method can be used to find whether a rule disable an AST node or not.

[jfmengels]

Disable comments are the bane of linters! Refuse to implement them!
https://www.youtube.com/watch?v=XjwJeHRa53A

(I'm half serious. We're not supporting them in elm-review, but JS and ESLint are probably ill-equipped to not have them)

[Boshen]

Disable comments are the bane of linters! Refuse to implement them! https://www.youtube.com/watch?v=XjwJeHRa53A

(I'm half serious. We're not supporting them in elm-review, but JS and ESLint are probably ill-equipped to not have them)

I've watched all your talks and all your blogs, I stand with your point.

ESLint spoiled developers to just throw disable comments everywhere, which is what I've been seeing internally.

Although I still need to implement it so people can transition to Oxc, I may be able to make something better, for example raise an error if an ignored rules is not catching any errors.

[jfmengels]

Glad I was able to convince you ❤️

I may be able to make something better, for example raise an error if an ignored rules is not catching any errors.

I think that's a great thing to have if disable comments are a thing. Ruff does this as well, so it seems like it's definitely doable.

[Boshen]

Code Fix

I will use the most basic text editing approach, mainly due to its simplicity. It's interesting to note that rust clippy also uses the text editing approach.

[charliermarsh]

Ruff uses a basic text editing approach. I based it on ESLint's model (rules can return a fix with an applicable range and the content to insert (which could be empty for deletions)). I know ESLint is now talking about supporting AST-aware autofix, but honestly I've been pretty happy with how this has worked out for Ruff. It's very simple and very flexible (I don't fully understand how AST-aware autofix would work with stylistic rules that don't touch the AST at all), and while it can introduce syntax errors in theory, it honestly doesn't come up much in practice.

A few things that've come up in Ruff:

1. Because fixes can conflict, and/or fixing one rule can create a new violation (e.g., removing a function call might lead to an import being unused), we run Ruff iteratively until there are no errors left to fix. It's not that efficient but it works well in practice. It does lead to some oddities whereby (e.g.) the number of errors we fix when run with --fix might not match the number of fixable errors that we flag in the first place.
2. We don't have any model for rules that require fixes at multiple codepoints (e.g., "Insert an import at the top of the file, then change this function call to this other function call").
3. Like Clippy, we detect if an autofix introduces a syntax error, revert the fix, and tell the user to file an issue. We do the same with autofix loops (fixing an error that leads to a new error that we then fix that restores the existing error), which should also be "impossible" but can come up if we have a poorly implemented fix or unintentionally-conflicting rules.
4. Related to (2)... in Python, an empty "body" is a syntax error, since Python relies on semantic whitespace rather than brackets to define scopes. So if we have an autofix that deletes a statement, we have to be careful not to leave its parent body empty (if deleting the statement would leave the parent empty, we insert replace it with a pass statement). This requires tracking deletions as we lint the file, even though some of those deletions may not ultimately be applied, e.g., if they conflict with other fixes and get deferred to the next fix pass. This is just a weird thing where there are some theoretical bugs and the semantic model is not very good. I don't think you'll have this problem but it bothers me a lot.

[Boshen]

🤣 code fixes seems to be harder than I thought, I think I'll remove it from the first MVP release.

I didn't know there are so many corner cases for code fixes, thank you for your valuable input!

[charliermarsh]

Haha don't be too intimidated! Sometimes it's good not to think about or even know about all the problems / cases in advance. We certainly didn't ship with support for all of these things, they were added over time.

[jfmengels]

elm-review is doing similar things as what @charliermarsh described above.

For (1), as soon we find a fix, we re-run the linter (as optimally as we can) to find new errors, and so on until there are no more. As @charliermarsh said, it's probably not the most efficient, but it avoids some weird results.

For (2), fixes for elm-review are a list of text edits (one edit being text removal, text insertion or text replacement). Fixes are applied in order from nearest-to-the-end to nearest-to-the-start of the end, and if there are overlap of some of the ranges, then the fix is canceled.
This simple system works greatly for us. At some point, I would like to have multi-file fixes (because the tool supports multi-file analysis).
I'd say that text-editing works very well in practice. If someone creates a AST-to-string library, then you can in practice simulate AST replacements.

I'm not doing (3) though. I've wanted it because it makes sense, but in practice we've never seen this happen so no user has asked for it (but we tend to have less contradictory rules that lead to this result).

About catching invalid fixes, elm-review's inner testing framework is extremely thorough in its checks. Basically, if your rule provides a fix in a given scenario, you have to indicate what you expect the fix to change the code into. And if the fix creates a syntax error or there is a different problem with the fix, tests will let you know. (The tests do a LOT of other things I've never seen other linter tests do, see https://twitter.com/jfmengels/status/1609231045118889984 and https://github.com/jfmengels/elm-review/blob/master/documentation/design/test-module.md)

[Boshen]

eslint-plugin-import

eslint-plugin-import, a.k.a multi-file linting.

This won't be part of the first MVP, but I already have a working solution internally. The code is not really nice to work with so I plan to redesign it later.

The working code currently utilizes module resolution (the Rust version of enhance-resolve which I also worked on) to build up ModuleRecords (defined in the ecma262 spec).

What I haven't figure out yet is to run the module resolution procedure in a memory efficient way. Because every module needs to wait for its dependencies to resolve, peek memory can go up to a 10GB in large monorepos.

[strager]

10 GB? 🤨 How big is each ModuleRecord?

[Boshen]

10 GB? 🤨 How big is each ModuleRecord?

I wrote that too quickly, I meant the whole program will peek to 10GB, because there will be thousands of ASTs waiting for their dependencies to resolve :-(

[jfmengels]

I'll be doing a write-up for how multi-file analysis works for elm-review, because it's in practice quite a complex feature with a lot of implications. I'll link it here when I'm done with it.

[jfmengels]

I finally did it: https://jfmengels.net/multi-file-analysis/
I can now close this tab 😅