BTW, I'm wondering why such implementation (impl<'a, A: Automaton + ?Sized> Automaton for &'a A) should exist. I'll open a PR to remove it if you don't mind.

That trait impl can't be removed. It's a breaking change.

I don't remember the precise reason it exists, other than to make &A implement Automaton. My recollection is that it was also related to avoiding monomorphization creating extra copies of some functions. But I am not confident in my methodology here.

As for the infinite loop, I think I need an MRE to determine whether the fault lies with this crate or not.

That trait impl can't be removed. It's a breaking change.

Fair.

As for the infinite loop, I think I need an MRE to determine whether the fault lies with this crate or not.

I don't think it's really reproducible out of the crate as Automaton is sealed. I was instrumenting the trait's implementation with some function that was casting self to a &dyn Automaton when I realized this unnecessary referencing exists.
You can try it with:

unsafe impl<'a, A: Automaton + ?Sized> Automaton for &'a A {
    #[inline(always)]
    fn start_state(&self, anchored: Anchored) -> Result<StateID, MatchError> {
        let _ = self as &dyn Automaton;
        // ...
    }
}

But it's basically an artificial problem!

Right. I absolutely agree that you can get an infinite loop during compilation if the trait implemented incorrectly.

But all righty, I'm going to close this as a non-issue for now. Thanks for looking into this!