Static analysis of large volumes of Python code: Instagram experience. Part 1

Our linting rules use the LibCST syntax tree to find patterns in code. This syntax tree, at a high level, is easy to explore, it allows you to get rid of the problems that accompany the work with the "irregular" language.

Suppose that in a certain module there is a cyclic dependency due to type import. Python solves this problem by putting type import commands in a block if TYPE_CHECKING. This is protection against importing anything during program execution.

# import value commands
from typing import TYPE_CHECKING
from util import helper_fn

# type import commands
if TYPE_CHECKING:
from circular_dependency import CircularType

Later, someone added another type import and another security block to the code. if. However, the one who did this might not know that such a mechanism already exists in the module.

# import value commands
from typing import TYPE_CHECKING
from util import helper_fn

# type import commands
if TYPE_CHECKING:
from circular_dependency import CircularType

if TYPE_CHECKING: # Duplication of the defense mechanism!
from other_package import OtherType

You can get rid of this redundancy using the rule of the linter!

Let's start by initializing the counter of “protective” blocks found in the code.

class OnlyOneTypeCheckingIfBlockLintRule (CstLintRule):
def __init __ (self, context: Context) -> None:
super () .__ init __ (context)
self .__ type_checking_blocks = 0

Then, meeting the corresponding condition, we increment the counter, and check that there would be no more than one such block in the code. If this condition is not met, we generate a warning in the appropriate place in the code, causing an auxiliary mechanism used to generate such warnings.

def visit_If (self, node: cst.If) -> None:
if node.test.value == "TYPE_CHECKING":
self .__ type_checking_blocks + = 1
if self .__ type_checking_blocks> 1:
self.context.report (
node
"More than one 'if TYPE_CHECKING' section!"
)

Similar linting rules work by looking at the LibCST tree and gathering information. In our linter, this is implemented using the Visitor pattern. As you may have noticed, rules override methods visit and leave methods associated with the type of node. These "visitors" are called in a specific order.

class MyNewLintRule (CstLintRule):
def visit_Assign (self, node):
... # is called first

def visit_Name (self, node):
... # called for each descendant

def leave_Assign (self, name):
... # called after processing all descendants

Visit methods are called before visiting descendants of nodes. Leave methods are called after visiting all descendants

We adhere to the principles of work, in accordance with which simple tasks are primarily solved. Our first linter rule of our own was implemented in a single file, contained one “visitor” and used a shared state.

One file, one “visitor”, using shared state

Class Single visitor must have information about the state and the logic of all our linting rules that are not related to it. Moreover, it is not always obvious which state corresponds to a particular rule. This approach shows itself well in a situation where there are literally a few of your own linting rules, but we have about a hundred of these rules, which made it very difficult to support the pattern. single-visitor.

It is difficult to know what state and logic are associated with each of the checks.

Of course, as one of the possible solutions to this problem, we could consider the definition of several “visitors” and the organization of such a work scheme that each of them would look at the whole tree each time. However, this would lead to a serious drop in productivity, and the linter is a program that should work quickly.

Each linter rule can repeatedly traverse a tree. When processing a file, the rules are executed sequentially. However, this approach, which often traverses the tree, would lead to a serious drop in performance.

Instead of realizing something like this, we were inspired by the linters used in ecosystems of other programming languages ​​- like ESLint from JavaScript, and created a centralized register of “visitors” (Visitor Registry).

Centralized register of "visitors". We can effectively determine which node is interested in each rule of the linter, saving time on nodes that are not interested in it.

When the linter rule is initialized, all overrides of the rule methods are stored in the registry. When we go around the tree, we look at all the registered “visitors” and call them. If the method is not implemented, it means that you do not need to call it.

This reduces the system’s consumption of computing resources when new linting rules are added to it. We usually check with a linter a small number of recently modified files. But we can check all the rules on the entire Instagram server code base in parallel mode in just 26 seconds.

After we resolved performance issues, we created a testing framework that was aimed at adhering to advanced programming techniques, requiring tests in situations where something should have some quality and in situations where something should not have some quality must.

class MyCustomLintRuleTest (CstLintRuleTest):
RULE = MyCustomLintRule

VALID = [
        Valid("good_function('this should not generate a report')"),
        Valid("foo.bad_function('nor should this')"),
    ]
    
    INVALID = [
        Invalid("bad_function('but this should')", "IG00"),
    ]

To be continued…

Dear readers! Do you use linters?