Optimizing rslint's no-shadow relation

[Kixiron]

This is a follow-up on the Gitter discussion for optimizing rslint's NoShadow relation

Instead of searching the entire subtree for shadowing variables, you can query for a variable declaration such that a variable with the same name is visible in the parent scope

I attempted this, but I run into the edge case of the top-level scope and I'm not entirely sure what to do. The clause I attempted was this

NoShadow(name, (initial_id, initial_span), (shadower_id, shadower_span), false, file) :-
    // Only do hoisted scopes when hoisting is enabled
    File(file, _, _, config),
    config.no_shadow_enabled() and config.no_shadow_hoisting(),

    // Get the shadowing variable
    VariableDeclarations(file, name, shadower_scope, Some { shadower_span }, shadower_id, false, false, _),

    // Make sure the shadower variable is able to be hoisted
    IsHoistable(shadower_id, file, true),

    // Get the hoisted scope of the shadowing variable
    FunctionLevelScope(shadower_scope, hoisted_scope, file, _),

    // See if a different name is in the scope preceding the hoisted one
    InputScope(parent_scope, hoisted_scope, file),
    NameInScope(file, name, parent_scope, initial_id),
    initial_id != shadower_id,

    // Get the shadowed variable
    VariableDeclarations(file, name, _, Some { initial_span }, initial_id, false, _, _),

    // Make sure the shadowing variable was declared after the initial.
    // This is counterintuitive, but is needed because of variable hoisting,
    // since the variable being shadowed occurs *before* the shadowing one
    initial_span < shadower_span.

After thinking about this significantly more, I don't think the rule as a whole is correct, since FunctionLevelScope is automatically applied to everything that needs hoisting. However, the remaining three rules miss some test cases and I'm not sure how to go about fixing them

NoShadow(name, (initial_id, initial_span), (shadower_id, shadower_span), false, file) :-
    // Only analyze a file if NoShadow is enabled
    File(file, _, _, config),
    config.no_shadow_enabled(),

    VariableDeclarations(file, name, initial_scope, Some { initial_span }, initial_id, false, true, _),
    ScopeFamily(initial_scope, child_scope, file),
    VariableDeclarations(file, name, child_scope, Some { shadower_span }, shadower_id, false, _, _),
    shadower_id != initial_id and initial_span < shadower_span.

NoShadow(name, (initial_id, initial_span), (shadower_id, shadower_span), false, file) :-
    // Only analyze a file if NoShadow is enabled
    File(file, _, _, config),
    config.no_shadow_enabled(),

    VariableDeclarations(file, name, _, Some { initial_span }, initial_id, false, _, UserDefined { initial_scope }),
    ScopeFamily(initial_scope, child_scope, file),
    VariableDeclarations(file, name, child_scope, Some { shadower_span }, shadower_id, false, _, _),
    shadower_id != initial_id and initial_span < shadower_span.

// Hoisted variables
NoShadow(name, (initial_id, initial_span), (shadower_id, shadower_span), false, file) :-
    // Only analyze a file if NoShadow is enabled
    File(file, _, _, config),
    config.no_shadow_enabled() and config.no_shadow_hoisting(),

    VariableDeclarations(file, name, initial_scope, Some { initial_span }, initial_id, false, false, _),
    VariableDeclarations(file, name, initial_scope, Some { shadower_span }, shadower_id, false, _, _),
    shadower_id != initial_id and initial_span > shadower_span.

These three rules (that all need optimization themselves to eliminate the ScopeFamily lookups) miss the following test cases

function foo(a) { } var a;
function foo(a) { } function a() {}
{ let a; } function a() {}
{ const a = 0; } function a() {}
function foo() { let a; } function a() {}
function foo() { var a; } function a() {}
function foo() { let a; } var a;
function foo() { var a; } var a;

The code is all located here

[ryzhyk]

Sorry, I don't fully understand the details of what you need to achieve vs what the code is doing at the moment. It sounds like the edge case you need to handle can be captured with the help of negation, along the lines of

// compute shadower_scope
...
// shadower_scope is a top-level scope
not FunctionLevelScope(shadower_scope, _, _, _),

There are more efficient ways to experss this, but this would be the idea.

Can you formulate the rule that you'd like to write (or how you'd like to alter the behavior of an existing rule), and I'll try to propose a solution?

[Kixiron]

That's a fantastic idea, I'm gonna work on this some

[Kixiron]

I implemented this and refactored VariableDeclarations, it's now significantly more maintainable but has the same test failures (code)

[ryzhyk]

Ok, let me try to understand on of these test failures, e.g., this one:

function foo(a) { } var a;

I can see how argument a shadows variable with the same name. Is this the issue you'd like to catch? If so, which rule is supposed to catch it? Or is the problem that you don't know how to write such a rule?

[Kixiron]

Yes, that's correct, the argument a shadows var a;. This should be being caught by NoShadow, but it isn't being for some reason and I can't figure out why

[ryzhyk]

Ok, great, so we just need to understand why the rule does not match the JS code example. Do my comments in you code below make sense?

    // Returns variable declaration `var a`.
    VariableDeclarations(
        file,
        name,
        scope,
        initial_id,
        &VariableMeta {
            .implicitly_declared = false,
            .declaration_span = Some { initial_span },
        },
    ),
    // `initial_scope` = top-level scope that contains both variable declaration and function?
    var initial_scope = if (config.no_shadow_hoisting()) {
        scope.hoisted_scope()
    } else {
        scope.unhoisted_scope()
    },

    // Ok, this is where I'm lost.  You're searching all declarations withing `initial_scope`. Since `initial_scope` only contains `var a`, so this does not return any matches, right?
    DeclarationVisibleWithin(file, initial_scope, shadower_id),
    // A declaration cannot shadow itself
    shadower_id != initial_id,

[Kixiron]

The first comment seems correct, with the addition that if .no_shadow_hoisting() is true, var a will have its hoisted scope assigned to it
I'm currently propagating DeclarationVisibleWithin, so initial_scope should contain var a and all previous declarations as well (I think?)

[ryzhyk]

If you go down the path of storing interned references instead of scope ids, then the scope object can contain the path to the scope and you can check that one path is a prefix of the other.

[Kixiron]

I'm not sure I understand what you mean, could you give an example?

[ryzhyk]

Will clarify when I'm back at my computer, but personally I prefer my other suggestion in the thread below.

[ryzhyk]

Here is an outline of how interned objects can be used to enforce that scopes are nested. Change the signature of DeclarationVisibleWithin from

relation DeclarationVisibleWithin(file: FileId, scope: ScopeId, declaration: AnyId)

to

relation DeclarationVisibleWithin(file: FileId, scope: Intern<Scope>, declaration: AnyId)

Let's assume that the Scope type contains enough information to check that one scope is nested within another scope. Then you can modify the rule to only match nested scopes:

    VariableDeclarations(
        file,
        name,
        scope,
        initial_id,
        &VariableMeta {
            .implicitly_declared = false,
            .declaration_span = Some { initial_span },
        },
    ),
    var initial_scope = if (config.no_shadow_hoisting()) {
         /* ASSUME THAT `hoisted_scope` AND `unhoisted_scope` RETURN `Intern<Scope>` RATHER THAN SCOPE ID.  */
        scope.hoisted_scope()
    } else {
        scope.unhoisted_scope()
    },
    DeclarationVisibleWithin(file, shadower_scope, shadower_id),
    shadower_scope.is_child_of(initial_scope), /* WE CAN COMPARE SCOPES NOW. */
    shadower_id != initial_id

Does this make sense?

[Kixiron]

Yes, I believe I understand

[ryzhyk]

Here's another method that I was trying to suggest from the start:

...
DeclarationVisibleWithin(parent_scope, decl1), // shadowed declaration
InputScope(parent_scope, child_scope),
VariableDeclaration(.scope = child_scope,  .name = decl1.name}). // shadowing declaration

[Kixiron]

And no ids are globally unique other than FileId, for each file (with its unique FileId) every ScopeId, ExprId, ... is unique, so the true id of something is more accurately reflected as (FileId, {Scope, Expr}Id)

[ryzhyk]

Recursive relations are already distinct'ed; otherwise recursion simply wouldn't converge. The problem is that distinct is itself a very expensive operator that internally constructs two arrangements of the input collection. The optimization I'm about to try, suggested by @frankmcsherry reduces the cost of distinct.

Note that duplicate values do not necessarily make things slower, as they will end up being stored as weights.

There is also consolidate operator that can reduce the memory footprint of a collection without changing its semantics. I've experimented with it in the past and it can both help and hurt the performance in different cases, so that would be another candidate for annotating relations or rules with.

[ryzhyk]

And no ids are globally unique other than FileId, for each file (with its unique FileId) every ScopeId, ExprId, ... is unique, so the true id of something is more accurately reflected as (FileId, {Scope, Expr}Id)

That's one avenue for optimization then. You can replace all id's with interned references to the object itself. Such references are globally unique, hence file ids will no longer be needed. When used as a join key, an interned reference behaves as a 64-bit identifier. This approach also has the important benefit that you can directly access object fields via the interned reference, i.e., you don't need to perform another join to open up the object. The main caveat is that you have to avoid cycles of references, similar to Arc's and Rc's in Rust.

[Kixiron]

I’m not sure how I’d do that, given the current structure of

relation Statement(file, id, ...)
relation SpecificKindOfStatement(file, id, ...)

I’ve been thinking of "compressing" ids into a [u32; 2] of [file, id] would that help things?

[ryzhyk]

I’ve been thinking of "compressing" ids into a [u32; 2] of [file, id] would that help things?

You might see some improvement; it's hard to tell.

I can see the problem with the current code structure. One alternative is to convert statements to enums:

typedef Statement = StatementKind1{...}
                               | StatementKind2{...}
                               | ...

or

typedef StatementKind = StatementKind1{...}
                                      | StatementKind2{...}
                                      ...
typedef Statement = Statement{ file, id, kind: StatementKind}

[Kixiron]

I've been reading a Systematic Approach to Deriving Incremental Type Checkers and it mentions some things about improving performance within chapter 4, but I'm not really sure how to extrapolate their very specific examples into ddlog with my codebase or even how to understand a lot of it

[Kixiron]

So, I've investigated further and after finding out that linting a single file of what's still a hefty length, my ddlog code is absurdly fast. I applied the id fusion optimization that combines things like ScopeId and FileId into one single id and that sped things up a bit, but after running some tests with persisting the ddlog instance and repeatedly re-running files I'm really convinced that the problem is data from different files slowing things down drastically. Is there any way to partition data within a single ddlog instance or otherwise make ddflow recognize them as logically distinct from each other?

[ryzhyk]

A couple of high-level thoughts:

I sincerely hope you will continue digging into the performance of DDlog on these benchmarks. This kind of detailed performance analysis is how we eventually make DDlog better, and we haven't done enough of it so far. However, as far as the evaluation of DDlog for use in your project goes, there are a few questions you may want to consider even as the performance work is still in progress:

1. Is the incremental performance good enough? If I understand the plan correctly, DDlog should enable RSlint to incrementally update static analysis results as the user keeps editing JS code in the IDE. So, initial indexing aside, is DDlog able to deliver the real-time responsiveness that you'd like to see in such a tool?

2. Maintainability. As you add more analyses, does DDlog enable you to implement them in a way that's easy to understand and maintain?

3. Is the non-incremental performance good enough? Although we're not happy with it, DDlog is able to index a large project in a few seconds. Since this is a one-off delay that only occurs on startup, and assuming the worst case scenario where we can't make it faster, is this performance acceptable?

4. How does the non-incremental performance compare to hand-optimized Rust code? You mentioned that scope analysis with DDlog dominates the runtime of RSlint. This might be because DDlog does not perform well or because this analysis is computationally harder than other RSlint checks. Do you happen to have the scope analysis implemented in Rust and how does that perform?

[Kixiron]

I'm working on getting the bench data, so stand by for that

Is the incremental performance good enough?

I haven't actually worked on this yet, I'm waiting on incremental re-parsing to be finished before implementing the incremental LSP segment of the code

Maintainability

It's rather nice to maintain once you get over the learning curve of datalog being datalog, logic languages require radically different ways of thinking about problems. This isn't really something that can be fixed (or is even bad), the learning materials could be better/more up to date though. The lack of tooling for things like unused code & only reporting one error at a time is a slight annoyance, but it's manageable. I will say that relations can interact in surprising ways if you don't keep track of what data is going where and debugging is difficult, but these are again manageable with some effort. Overall though it's really nice to work with, the rules more or less write themselves

Is the non-incremental performance good enough?

The latency isn't ideal for this particular project as it's aiming to be a blisteringly fast linter, it probably wouldn't be as large of a problem in a more traditional compiler. I think the latency will justify itself in the long term once more types of analyses have been implemented and even if it can't get any faster I think in the long term it could still be justified once more kinds of analyses are implemented.

How does the non-incremental performance compare to hand-optimized Rust code?

SWC has a scope analyzer implemented in Rust and it runs in the ballpark of 1/2 a second. Right now for rslint the scope analysis is by far the most intensive thing happening, the rest of the runtime runs in tens of milliseconds, which unfortunately makes ddlog's runtime all the more noticeable

[ryzhyk]

Ok, so tooling needs to be better, fair enough.

Please report holes in documentation whenever you run into any.

SWC has a scope analyzer implemented in Rust and it runs in the ballpark of 1/2 a second

Ok, so hand-optimized Rust is about 10x faster than DDlog. It would be nice to get within the 2x/3x range, I wouldn't expect to be able to do much better than that. Still, 1/2 second is an order of magnitude more than 10s of milliseconds for the rest of the analysis, so this is indeed the most expensive part that will dominate the runtime no matter what.

[Kixiron]

1-2 seconds is probably with an acceptable range, as long as things scale nice and easily it's no problem

[Kixiron]

Alright, I fixed some things up, pushed some code and got the profile for the hot region of scope analysis. Got it down to ~4 seconds, I'd really like to halve that if at all possible. I sped things up a little by removing global variables from NameInScope and making them a delayed antijoin on anything that actually needs to know about them, but I'm about out of ideas
Profile
Code