How do I tell the type checker that any subclass of ast.expr is ok?

[hunterhogan]

I'm so confused and frustrated that I don't know if I am asking the right questions.

Here is an example problem:

Argument of type "(hasDOTid) -> hasDOTid" cannot be assigned to parameter "action" of type "(expr) -> expr" in function "funcAttribute"
  Type "(hasDOTid) -> hasDOTid" is not assignable to type "(expr) -> expr"
    Parameter 1: type "expr" is incompatible with type "hasDOTid"
      "expr" is not assignable to "Name" Pylance (reportArgumentType)

The relevant code

Offending statement

    listIdentifiersCalledFunctions: list[ast_Identifier] = []
    findIdentifiersToInline = NodeTourist(findThis = IfThis.isCallToName
                            , doThat = Grab.funcAttribute(Grab.idAttribute(cast(Callable[[ast_Identifier], ast_Identifier], Then.appendTo(listIdentifiersCalledFunctions)))))
    findIdentifiersToInline.visit(FunctionDefToInline)

From this module.

The function

class Grab:
    ...

    @staticmethod
    def funcAttribute(action: Callable[[ast.expr], ast.expr]) -> Callable[[hasDOTfunc], hasDOTfunc]:

        def workhorse(node: hasDOTfunc) -> hasDOTfunc:
            node.func = action(node.func)
            return node
        return workhorse
    ...

    @staticmethod
    def idAttribute(action: Callable[[ast_Identifier], ast_Identifier]) -> Callable[[hasDOTid], hasDOTid]:

        def workhorse(node: hasDOTid) -> hasDOTid:
            node.id = action(node.id)
            return node
        return workhorse

From this module.

The types

ast_Identifier: typing_TypeAlias = str
hasDOTfunc: typing_TypeAlias = ast.Call
hasDOTid: typing_TypeAlias = ast.Name

Mostly from this module.

One "fix"

    listIdentifiersCalledFunctions: list[ast_Identifier] = []
    findIdentifiersToInline = NodeTourist(findThis = IfThis.isCallToName
                            , doThat = Grab.funcAttribute(cast(Callable[[ast.expr], ast.expr], Grab.idAttribute(cast(Callable[[ast_Identifier], ast_Identifier], Then.appendTo(listIdentifiersCalledFunctions))))))
    findIdentifiersToInline.visit(FunctionDefToInline)

Without cast, the type is effectively Callable[[ast.Name], ast.Name]. Since Name is a subclass of expr, I want the type checker to tell me that this is a valid statement. I mean, cast is not a fix here because there isn't an error. The problem is that I haven't defined something in such a way that the type checker understands that Callable[[ast.expr], ast.expr] includes subclasses of ast.expr.

[Daverball]

The complaint of the type checker is perfectly valid, since what you're doing is not type safe.

I think what's tripping you up here is variance. While a return type is covariant, i.e. you can assign a function with a return type that is a subtype of the original function, the inverse is true for argument types, since they are contravariant.

Consider the following example for covariance and contravariance:

def foo(x: str) -> object:
    return object()

def bar(x: object) -> str:
    return ""

x: Callable[[object], object] = bar  # this is safe, since `str` is also an `object`
y: Callable[[str], str] = bar  # this is also safe, since if your function can deal with `object` it can also deal with `str`
z: Callable[[object], str] = foo  # this is not safe, your function can only deal with `str` but you're claiming it can accept `object`
w: Callable[[str], str] = foo # this is not safe, you're claiming the function will return a `str` but it may actually return any `object`.

Or in other terms Callable[[T], T] means that T is invariant, since either you're violating the covariance of the return type or the contravariance of the argument type if you change what type T is.

What you can do however to solve this is to make funcAttribute generic (I'm using PEP 695 generic syntax for brevity, but you can also just define a TypeVar with bound=ast.expr):

def funcAttribute[T: ast.expr](action: Callable[[T], T]) -> Callable[[hasDOTfunc], hasDOTfunc]:

This way it will accept any callable that processes any node type that is either ast.expr or a subclass thereof.

[Daverball]

It is worth noting though that you are still not really type safe this way, since node.func is an ast.expr, so it's not safe to assume that it's something else and that your function will be able to deal with it.

[Daverball]

Or to put it another way: The way you're ensuring your doThat is actually safe is using your findThis, which ensures that func.expr is always an ast.Name, but the way the logic is structured there is no way for the type checker to know that findThis ensures an invariant on the doThat expression, that would allow funcAttribute to accept a callable that operates on ast.Name rather than ast.expr.

Predicate based APIs that operate on deeply nested data structures are inherently not particularly well-suited for static analysis. There are some limited things you can do with generics and TypeIs/TypeGuard, but your example goes far beyond what a static type checker efficiently would be able to prove.

So you essentially have two options:

1. Do the thing you already showed as a potential fix: Use cast to tell the type checker about invariants you've ensured in a way that the type checker doesn't understand
2. Make your functions less type safe and let them accept actions that might be unsafe, using e.g. the generic approach above, trusting that users of the API will make sure the passed in actions are actually safe.

Quite often you'll have to make trade-offs between false positives and false negatives with static analysis, if you encounter a lot of false positives because your API is too difficult to understand for static type checkers, then it might be worth making the API less type safe, even if that means you will now have false negatives and the type checker is helping you less than it was before.

[hunterhogan]

I greatly appreciate how much information you have given me. While I think I understand the stack and how the interpreter handles identifiers, objects, and execution, type checking is still a black box to me. Therefore, I struggle to understand where the disconnections are. Understanding different options is challenging, too. I am working through what you wrote to understand the terms of art and technical options. I've also decided to make this less complicated by requiring Python >= 3.12 in the package.

Disorganized thoughts, reactions, and information:

"Type safe" is a strange term of art to me. When I or other people use the package, I want the type checkers (and language servers) to be helpful guides. With type checkers, I too often feel like I'm a student being "taught" in a 1935 Catholic school by a nun holding a paddle.

Prototype of an old idea to subclass composable methods so that typing information can extend beyond the top level of the ast node.

class ImaCallToName(ast.Call):
    func: ast.Name

I made that subclass prototype before I made

class ClassIsAndAttribute:
    ...
    @staticmethod
    def funcIs(astClass: type[hasDOTfunc], attributeCondition: Callable[[ast.expr], bool]) -> Callable[[ast.AST], TypeGuard[hasDOTfunc] | bool]:

        def workhorse(node: ast.AST) -> TypeGuard[hasDOTfunc] | bool:
            return isinstance(node, astClass) and attributeCondition(node.func)
        return workhorse
    ...

I can't remember how I used it, but it's in the repo, of course (in mapFolding, here's a commit that includes it). I used the class in a TypeGuard antecedent, and ... (I can't communicate very well right now.)

In short, it seemed to work very well. If identifier, node, had been verified by TypeGuard as ast.Call and I had additionally checked that node.func was ast.Name... wait, I remember a detail:

class IfThis:
    ...

    @staticmethod
    def isCallToName(node: ast.AST) -> TypeGuard[ImaCallToName]:
        return Be.Call(node) and Be.Name(DOT.func(node))

    ...

If I used the above antecedent, and used the ImaCallToName subclass in later antecedents or actions, it had two effects: the TypeGuard of node as ast.Call was preserved even when it normally wouldn't be, and the type information of node.func would be preserved as ast.Name, which was fantastic.

That exact way of implementing is a combinatorics nightmare, though. To cover all cases, the quantity of necessary classes = sum of (for each class: for each attribute: attribute * number of valid types). If an attribute has type ast.expr, for example, then there are 27 valid types just for that attribute. I estimated 1773 subclasses.

TypeGuard / TypeIs

I don't know if I am using TypeGuard correctly or to its full potential. I have no clue how to use TypeIs.

Other Python tools

With help from this forum, I implemented my first generic after many failed attempts. I have implemented TypeVar with some success exactly twice despite dozens of attempts. Protocol? pfft.

A little context

I didn't mention in this thread that I don't have formal training as a programmer or professional programming experience. I started with line basic on a Vic-20 when I was 10 years old, but I am not a programmer. I did get a 53rd-percentile score on the Comp Sci GRE Subject Exam 20 years ago, which is strong evidence that I know the difference between a programmer and a person with a lot of computer knowledge. I worked in IT for 9 years, but sys/net admin, webmaster!, and teaching.

[Daverball]

I can understand your frustration. Python is a very dynamic language. A static type system is kind of antithetical to this. The Python type system being gradual helps, but it also makes it a lot harder to reason about type safety, which you need to be able to do on some level in order to get the most out of type hints (proportional to how many advanced typing features you're using, like generics or how complex your API is in terms of things like using higher order functions). But the point is the language and the type system are pulling you in slightly different directions in how you write your code.

I've spent the better part of the past five or so years writing a lot of typed Python code, as well as adding type hints to existing code bases and writing third party stub files and I still don't always succeed expressing some non-trivial type relationships, especially not on the first try and especially if the API is set in stone and it's not well suited for static typing. It takes a lot of experience to find good trade-offs between something that is type safe enough to help you find bugs, while not being so awkward to use, that nobody wants to use those type hints.

---

Yeah, you can certainly do things with TypeGuard and Protocol or pseudo-subclasses that have exactly the shape you need, so you can propagate nested type information further down the call stack of your higher order functions, but as you've pointed out the combinatorics quickly make this untenable to maintain. For some patterns it's currently just better or even necessary to give up a little bit of type safety and allow an Any to slip in here or there, to preserve the sanity of people that want to use your API and your own.

---

TypeIs is a more powerful version of TypeGuard that lets the type checker narrow in the negative case, so it's closer to how type checkers deal with isinstance(x, T) calls where they will infer the type kind of like this:

x: int | str
if isinstance(x, str):
    reveal_type(x)  #  (int | str) & str => str
else:
   reveal_type(x )  # (int | str) & ~str => int

A TypeGuard is more simple and will change the type to exactly what the TypeGuard says and only in the positive case, not in the negative case. You have to be more careful with TypeIs[T], since you have to make sure that your function returns True for exactly the set of all possible values described by the type T. If there is a mismatch the type checker will end up making unsafe narrowing decisions.

A good example of an unsafe TypeIs function is the following:

def is_int(x: object) -> TypeIs[int]:
    return isinstance(x, int) and not isinstance(x, bool)

Here you're excluding True and False from the set of objects of type int, even though they're both valid int instances, since bool is a subclass of int, so if you pass a bool into this function, the type checker will incorrectly narrow the negative case to Never, since a bool that isn't an int cannot exist.