This is more of a curiosity than anything, but as I'm learning more about impl
s, I'm wondering how Rust can lookup functions performantly.
What I mean is, let's say that I have an expression like this:
SomeType::foo()
So it seems like to identify foo
you would have to look up:
-
All intrinsic
impl
s:impl SomeType { ... }
-
All the traits
SomeType
conforms to:impl SomeTrait for SomeType { ... }
-
All the generic impls on traits
SomeType
conforms to:impl SomeOtherTrait for T
where T: SomeTrait
So to cover the first and the second case, this seems pretty manageable, but when you get to the third case, it just seems like the lookup space can become huge. Especially if you have traits which are defined super generally, like implemented on all types implementing Debug
.
It seems like the complexity of function lookup would reach something like (no. function calls) * (no. impls).
Am I thinking about this in the right way? Or else how does rustc accomplish this without being super slow?