How a Python type checker decides a variable is unused
x = 1 is unused only if no read of x resolves to that assignment. In Python, that read may sit inside a nested function or comprehension. A later assignment can also determine which x the read refers to.
I ran into these cases while adding unused-variable dimming to ty, Astral's Python type checker written in Rust.
The way it works is that ty finds local bindings nobody reads, and its language server tells the editor to dim them. By binding I mean any place where a name gets a value, so not only assignments but also parameters and loop variables.
How ty tells the editor what to dim
When you have the ty extension installed, the editor and ty talk to each other over the Language Server Protocol (LSP), and ty sends a diagnostic for every unused binding it finds. A simplified version of the payload looks like this:
{
"message": "`x` is unused",
"range": {
"end": { "character": 5, "line": 1 },
"start": { "character": 4, "line": 1 }
},
"severity": DiagnosticSeverity.Hint,
"source": "ty",
"tags": [DiagnosticTag.Unnecessary]
}DiagnosticTag.Unnecessary and DiagnosticSeverity.Hint give the quietest level the protocol has. The range covers only the binding (x), not the whole line. Every editor decides how to dim it, though some let you configure it. In VS Code it's normally dimmed.
Binding is not only about =
My first implementation walked the file's abstract syntax tree (AST), which is how ty represents the parsed Python code, and for every place in the syntax that could create a local name, it looked in ty's semantic model to check if it was used. It worked fine on tens of examples I came up with.
The problem was finding all the possible candidates. For that, you need to know what counts as a binding, and in Python it's not just =:
# parameters
def func(x): ...
# variable in loop or comprehensions
for item in items: ...
nodes = [n * n for n in rows]
# context managers and exception handling
with open(path) as f: ...
try: ...
except ValueError as exc: ...
# walrus
if (count := len(items)) > 3: ...
# match pattern
match event:
case {"type": kind}: ...Each of the cases needed its own treatment, which was a lot of code for something ty mostly knew already.
Instead, the final merged version goes over the definitions that ty already knew about.
Annotations, like x: int, only declare a type, so you can only tell they're unused if no one reads them in the scope at all.
Tracking which bindings are read
@carljm suggested recording usage in the place where ty already builds its definition usage map. Most of what I needed was already there.
def f(flag):
x = 1 # dimmed
x = 2
if flag:
y = 1
else:
y = 2
print(x, y)Technically, no one read x while it was 1. The print only sees its value of 2, so x = 1 is marked unused. With conditional branches, like with y, both are used because you can't prove otherwise.
The simplest option was to track usage in a separate boolean table next to the map of definitions.
struct UseDefMapBuilder<'db> {
all_definitions: IndexVec<ScopedDefinitionId, DefinitionState<'db>>,
used_bindings: IndexVec<ScopedDefinitionId, bool>,
}
impl<'db> UseDefMapBuilder<'db> {
fn record_read(&mut self, bindings: &Bindings) {
for binding in bindings.iter() {
let id = binding.binding;
if !id.is_unbound() {
self.used_bindings[id] = true;
}
}
}
}Now the separate unused_bindings query used for dimming no longer figures out usage itself but relies on stored earlier results.
How do you actually find the binding?
You can read a variable from a different scope compared to where it's bound. Here's an example with a closure:
def outer():
x = 1
def inner():
return x
return innerWhen ty sees x inside inner, it has to figure out which x it is. In this case it's the x = 1 from outer, so that binding in outer gets marked as used.
Python also has nonlocal, which tells that x in mid is not a new local variable, so assignments there go to outer's x.
def outer():
x = 1
def mid():
nonlocal x
x = 2
def inner():
return x
return inner
return midSo mid has no x of its own. x = 2 is still a binding, but it belongs to outer, and the read inside inner refers to that same variable.
global works in a similar way but sends assignments to the module scope, and since this feature only looks at local bindings, ty doesn't report those.
Comprehensions have their own scope, and they can be inside a function that is itself inside another function.
def outer(i: int):
def inner():
return [[n for n in range(i)] for _ in range(2)]
return innerHere i is read inside the comprehension, which is two scopes away from the parameter in outer, so ty has to go through both before the parameter counts as used.
The tricky part is that when you see a read, you don't always know its scope yet.
def outer():
x = 0
def middle():
def inner():
return x
x = 1
return inner
return middleYou can only tell which names are local by looking at the whole function body, so the x = 1 that comes later still makes x local to middle. That means inner captures middle's x, and x = 0 in outer is really unused.
That's why ty resolves captures after finishing a scope. Reads it can't resolve go to the parent and keep moving up the hierarchy until ty reaches a finished scope that owns the name and can mark its binding as used.
Unused doesn't mean removable
Some parameters are unused by all the rules above, but flagging them would just annoy people, so the feature skips the usual placeholders:
from typing import overload
@overload
def func(val: int) -> int: ... # overload, parameters not reported
class Worker:
def handle(self, event): # self not reported
... # body is just ..., so event not reported
def poll(self):
_ = self.checkpoint() # names starting with _ not reportedIn stub files every body is a placeholder anyway, so parameters there are never flagged.
An override may need a parameter to match the base method's signature, even if it never reads it:
class Base:
def handle(self, event):
print(event)
class Child(Base):
def handle(self, event): # event is dimmed here
return 0ty dims event in Child.handle because it's unread. Removing it would break the override, though. Somewhere in the middle of iterating on feedback, I suppressed unused parameters in methods that override a base-class method, but @carljm suggested that this only works in one direction: a base method can have a parameter unused while the method overriding it needs it. To make it fully correct, you have to figure out if subclasses override the method, or limit the implementation to final methods and classes.
In the end I removed the suppression, so ty now dims an override parameter when the method body never reads it, which is also what Pylance does. As @MichaReiser put it, a false positive here doesn't do much harm. The hint only says that no read resolves to this binding, whether you can remove it is a different question.
Why it stops at functions
The initial version of the feature reported unused bindings only inside functions, lambdas and comprehensions. A read of a function's variable can't suddenly happen from the scope enclosing it, only from its own scope or a nested one.
Taking the behaviour to the module scope makes it more challenging to agree on false positives and false negatives. Another file can import or re-export a module level attribute. Even a class scope can be accessed from outside.
You can handle that too, but you'll need to support analysis across files. On top of the complexity it adds to the feature, it can also affect non-functional requirements, like increased memory usage and degraded performance, which may not be worth it for a dimming feature.