> the trait can be implemented multiple times on the same type, with different A

That was the intention - a function that dispatches on the type of both arguments (it probably shows that I secretly think of traits as typeclasses). I'm still trying to figure out what the implications of the above choices are.

> In more complicated situations coherence may disallow one or more of those choices.

I hadn't thought of that. If the trait is in another crate, does coherence require that the self type is in this crate or that all the types are in this crate? How do the coherence rules work if I don't have self type?