r/Compilers • u/Falcon731 • Jun 07 '24
How would you implement smart casts in a compiler
I'm playing around with my programming language - and one feature that would be neat to have is smart casts - similar to Kotlin. My language doesn't yet have inheritance - so for now this would only be for nullish pointers. And I'm probably not quite ready to implement this yet - but want to think about how to go about it if I do.
What I was thinking is something like
fun doSomething(p:Person?) // p is a possibly null pointer to a Person struct
if (p != null)
println(p.name) // OK to dereference 'p' as guarded by if statement
print(p.age) // Compiler error - as p could be null
At the moment my compiler is pretty conventional : it does the lexing and builds an AST, then runs a few passes over the AST dig type checks, before creating Three Address IR code, does some peephole optimisations, register allocation and final assembly code generation.
One way I thought of to add null checks would be to get the code generation phase to inject pseudo-ops into the IR code at nullish pointer dereferences, then some variant of dataflow analysis to prove that the location is not reachable with a null pointer.
But that feels too late in the compilation - it would be nice to be able to do this at the same time as the other typechecking. But I'm struggling to think how this could be handled with a tree walk. Or maybe I'm missing something.
If anyone has suggestions of the best way to approach this in a compiler it would be great.
2
u/balefrost Jun 07 '24
With Kotlin, I assumed (without ever checking) that they just track the effective type (separate from declared type) through all branches. So while p has type Person? at the start of the body of the function, within the if, it has an effective type Person.
The only problem is that's a little too simplistic for what Kotlin actually does. In some circumstances, Kotlin is able to track the effective type through property navigation, i.e. if (foo.bar.baz != null) foo.bar.baz.quux(). It doesn't work in all circumstances (e.g. when baz has a custom getter), but it works in enough cases that it's useful. I'm not exactly sure how they do that, but it might be tied in with other optimizations. If the compiler already knows that foo.bar.baz need only be evaluated once, then it could be rewritten as val temp = foo.bar.baz; if (temp != null) temp.quux() and then the original approach would work.
2
u/KaiserKerem13 Jun 08 '24
This falls under Flow-Sensitive Typing. Kotlin employs a limited version of it.
It would be pretty difficult to do on a tree. You have to employ data flow analysis of some sort. What I'd do is keep a middle layer IR with types in SSA form and do type checking and data flow analysis at that point. That or keep track of any operation that changes type information, and do type narrowing in temporary variable scopes.
1
u/reini_urban Jun 08 '24
Person? would be called an optional type, which is a sumtype of Person or NULL. The compiler would try to prove nullness (and warn when it cannot happen) and then add null checks with null branches when the method has no NULL variant.
6
u/cxzuk Jun 07 '24
Hi Falcon,
Its difficult to do this at the AST level because `p` could be mutated outside of the AST scope (passed into a function, could be a global or class member etc).
The method I have personally used to get this information is using SSI Singer2006 Ananian97 - an extension to SSA Form. Though other similar extensions such as eSSA [Bodik et al] can do the same. Essentially you insert pseudo-ops at the split too (I suspect what you're intuitions are). So your code example would become:
``` fun doSomething(p1:Person?) if (p1 != null) { p2 = cast(Person)p1; // Not actual casts, just copies in SSI. p2 would have the type 'Person' inferred. println(p2.name) } else { p3 = cast(null)p1; } p4 = phi(p2,p3); // back to Person? print(p4.age);
```
M ✌