How does rustc lookup functions?

[spencerkohan]

This is more of a curiosity than anything, but as I'm learning more about impls, 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:

1. All intrinsic impls:

   impl SomeType { ... }

2. All the traits SomeType conforms to:

   impl SomeTrait for SomeType { ... }

3. 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?

[alice]

I mean once you notice that you only have to decide between generic impls that contain a function of the name you used, the full set is going to be pretty small. Especially since the trait has to be in scope.